Routing Flexibility in Job Shop Scheduling Problem – A Genetic Algorithm Approach

International Journal of Research and Scientific Innovation (IJRSI) | Volume V, Issue XI, November 2018 | ISSN 2321–2705

Routing Flexibility in Job Shop Scheduling Problem – A Genetic Algorithm Approach

Suresh Holi^#1, B P Shivakumar*

 ^# Research Scholar, Department of Mechanical Engineering, JSS Academy of Technical Education, Bengaluru,  affiliated to Visvesvaraya Technological University, Belagavi, INDIA
*Department of Mechanical Engineering, JSS Academy of Technical Education, Bengaluru, INDIA
¹Corresponding Author

Abstract – The paper presents a Genetic Algorithm (GA) approach to solve Job Shop Scheduling Problem (JSSP) with Sequence Dependent Setup Times (SDST) and assess the effect of routing flexibility on makespan performance measure. Two case studies of size five part types, five machines and ten part types, ten machines are taken into consideration. Results are generated for different routing flexibilities in a manufacturing scenario wherein setup times are comparable to operation processing times. It indicates that routing flexibility has some effect on makespan performance measure.

Keywords -job shop scheduling; sequence dependent setup time; genetic algorithm; makespan; routing flexibility.

I. INTRODUCTION

Scheduling in many manufacturing and service industries involves decision-making to allocate resources to tasks thereby optimizing the objectives and achieving the goals of the organization [1]. In the classical job shop scheduling problem ‘n’ jobs are to be processed on ‘m’ machines. For everyjob to be processed, the sequence of operations performed on a set of machines follow a particular order and each of the machine processes at most one operation at a time. In job shop scheduling, only sequencing of jobs on machines is done and there are no alternative machines for the operations. An extension of classical job shop problem, known as flexible job shop problem, allows operations to be processed on any amongst available machines to achieve better schedule [2] – [4]. The scheduling problem further gets complex with introduction of alternative machines as not only sequencing, also, job routes need to be decided.

Read More