《2016 A fast heuristic algorithm for solving parallel-machine job-shop scheduling problems》.pdf

Int J Adv Manuf Technol (2014) 70:531–546 DOI 10.1007/s00170-013-5281-6 ORIGINAL ARTICLE A fast heuristic algorithm for solving parallel-machine job-shop scheduling problems Omid Gholami · Yuri N. Sotskov Received: 4 May 2013 / Accepted: 29 August 2013 / Published online: 18 September 2013 © Springer-Verlag London 2013 Abstract We consider a multistage processing system, Keywords Scheduling · Flexible job-shop · Makespan · which includes both identical (parallel) machines that can Heuristic process the same set of operations and different machines that can process only different operation sets. A release time r is given for each job J to be processed. For such a pro- 1 Introduction i i cessing system, we minimize the makespan, i.e., problem IJ |r |C is considered. The problem IJ |r |C is an In a job-shop problem denoted as J |r |C (see [13] for i max i max i max extension of the classical job-shop problem J |r |C for the three-field notation used for the machine scheduling i max the case when parallel (or identical) machines are also given. problems), n jobs of set J have to be processed on set Both problems J |r |C and IJ |r |C are strongly NP- M of m machines. A job Ji ∈ J is available for pro- i max i max hard. A mixed graph model used for solving the problem cessing from a release time ri ≥ 0. Processing of a job J |r |C is generalized for the problem IJ |r |C . Using Ji ∈ J consists of ni sequential non-devisable