Abstract
This paper develops a scheduling algorithm for the job shop scheduling problem with parallel machines and reentrant process. This algorithm includes two major modules: the machine selection module (MSM) and the operation scheduling module (OSM). An order has several jobs and each job has several operations in a hierarchical structure. The MSM helps an operation to select one of the parallel machines to process it. The OSM is then used to schedule the sequences and the timing of all operations assigned to each machine. A real-life weapons production factory is used as a case study to evaluate the performance of the proposed algorithm. Due to the high penalty of delays in military orders, the on-time delivery rate is the most important performance measure and then makespan is the next most important measure. Well-known performance measures in the scheduling literature, such as maximum lateness and average tardiness, are also evaluated. The simulation results demonstrate that the MSM and OSM using the combination of earliest due date (EDD), the operations’ lowest level code (LLC) of the bill of materials (BOM), and the longest processing time (LPT) outperforms the other scheduling methods.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Allahverdi A, Al-Anzi FS (2006) A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times. Eur J Oper Res 169(3):767–780
Allahverdi A, Gupta JND, Aldowaisan T (1999) A review of scheduling research involving setup considerations. OMEGA 27(2):219–239
Baykasoğlu A (2002) Linguistic-based meta-heuristic optimization model for flexible job shop scheduling. Int J Prod Res 40(17):4523–4543
Brucker P, Schlie R (1990) Job-shop scheduling with multi-purpose machines. Computing 45(4):369–375
Centeno G, Armacost RL (2004) Minimizing makespan on parallel machines with release time and machine eligibility restrictions. Int J Prod Res 42(6):1243–1256
Chan FTS, Wong TC, Chan LY (2006) Flexible job-shop scheduling problem under resource constraints. Int J Prod Res 44(11):2071–2089
Chen JC, Chen C-W, Dai J-Y, Tyan JC (2004) Dynamic state-dependent dispatching for wafer fab. Int J Prod Res 42(21):4547–4562
Chen JC, Chen C-W, Lin CJ, Rau H (2005) Capacity planning with capability for multiple semiconductor manufacturing fabs. Comput Ind Eng 48(4):709–732
Choi I-C, Choi D-S (2002) A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups. Comput Ind Eng 42(1):43–58
Hu TC (1961) Parallel sequencing and assembly line problems. Oper Res 9(6):841–848
Hurink J, Knust S (2001) List scheduling in a parallel machine environment with precedence constraints and setup time. Oper Res Lett 29(5):231–239
Kalir AA, Sarin SC (1999) The role of advanced start and dominance rules in simulated annealing for parallel processor scheduling problems. Prod Plan Control 10(8):757–766
Kim YK, Park K, Ko J (2003) A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Comput Oper Res 30(8):1151–1171
Kurz ME, Askin RG (2001) Heuristic scheduling of parallel machines with sequence-dependent set-up times. Int J Prod Res 39(16):3747–3769
Law AM, Kelton WD (2000) Simulation modeling and analysis, 3rd edn. McGraw-Hill, New York
Mastrolilli M, Gambardella LM (2000) Effective neighbourhood functions for the flexible job shop problem. J Sched 3(1):3–20
Norman BA, Bean JC (1999) A genetic algorithm methodology for complex scheduling problems. Nav Res Logist 46(2):199–211
Pierreval H, Mebarki N (1997) Dynamic scheduling selection of dispatching rules for manufacturing system. Int J Prod Res 35(6):1575–1591
Saidi-Mehrabad M, Fattahi P (2007) Flexible job shop scheduling with tabu search algorithms. Int J Adv Manuf Technol 32(5–6):563–570
Subramaniam V, Lee GK, Hong GS, Wong YS, Ramesh T (2000) Dynamic selection of dispatching rules for job shop scheduling. Prod Plan Control 11(1):73–81
Wang MY, Sethi SP, van de Velde SL (1997) Minimizing makespan in a class of reentrant shops. Oper Res 45(5):702–712
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, J.C., Chen, K.H., Wu, J.J. et al. A study of the flexible job shop scheduling problem with parallel machines and reentrant process. Int J Adv Manuf Technol 39, 344–354 (2008). https://doi.org/10.1007/s00170-007-1227-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-007-1227-1