American Institute of Mathematical Sciences

• Previous Article
A parallel water flow algorithm with local search for solving the quadratic assignment problem
• JIMO Home
• This Issue
• Next Article
Closed-loop supply chain network equilibrium model with retailer-collection under legislation
January  2019, 15(1): 221-233. doi: 10.3934/jimo.2018040

A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking

 1 School of Economics and Management, University of Electronic Science and Technology of China, Chengdu 611731, China 2 School of Economics and Management, Fuzhou University, Fujian Province 350108, China 3 School of Mathematical Sciences, Queensland University of Technology, 2 George St, Brisbane Queensland 4001, Australia

* Corresponding author: Shi Qiang Liu

Received  May 2017 Revised  November 2017 Published  January 2019 Early access  April 2018

Fund Project: This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 71571032, 71531003, 71572156 and 71572030.

In this paper, the blocking conditions are investigated in permutation flow shop, general flow shop and job shop environments, in which there are no buffer storages between any pair of machines. Based on an alternative graph that is an extension of classical disjunctive graph, a new and generic polynomial-time algorithm is proposed to construct a feasible schedule with a given job processing sequence, especially for satisfying complex blocking constraints in multi-stage scheduling environments. To highlight the state-of-the-art of the proposed algorithm, a comparative analysis is conducted in comparison to two other constructive algorithms in the literature. The comparison shows that the proposed algorithm has the following advantages: $i$) it is more adaptive because it can be applied to three different types of scheduling problems (i.e., permutation flow-shop, general flow-shop and job-shop) without any modifications; $ii$) it is able to quickly evaluate whether a schedule is feasible (acyclic) or infeasible (cyclic) through checking the availability of the topological order in a directed alternative graph model; $iii$) it is able to determine the critical path which is useful to design the neighborhood moves in the development of metaheuristics.

Citation: Pengyu Yan, Shi Qiang Liu, Cheng-Hu Yang, Mahmoud Masoud. A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking. Journal of Industrial and Management Optimization, 2019, 15 (1) : 221-233. doi: 10.3934/jimo.2018040
References:
 [1] I. N. K. Abadi, N. G. Hall and C. Sriskandarajah, Minimizing cycle time in a blocking flowshop, Oper. Res., 48 (2000), 177-180.  doi: 10.1287/opre.48.1.177.12451. [2] D. Bai, M Tang, Z. H. Zhang and E. D. R. Santibanez-Gonzalez, Flow shop learning effect scheduling problem with release dates, Omega, (2017).  doi: 10.1016/j.omega.2017.10.002. [3] K. R. Baker and T. Dan, Principles of Sequencing and Scheduling, Wiley Publishing, 2009. doi: 10.1002/9780470451793. [4] P. Brucker and T. Kampmeyer, Cyclic job shop scheduling problems with blocking, Annals of Operations Research, 159 (2008), 161-181.  doi: 10.1007/s10479-007-0276-z. [5] R. L. Burdett and E. Kozan, An integrated approach for scheduling health care activities in a hospital, European Journal of Operational Research, 264 (2018), 756-773.  doi: 10.1016/j.ejor.2017.06.051. [6] X. Cai, X. Wu and X. Zhou, Optimal Stochastic Scheduling, Springer, CA, USA, 2014. doi: 10.1007/978-1-4899-7405-1. [7] X. Cai, X. Wu and X. Zhou, Stochastic scheduling on parallel machines to minimize discounted holding costs, Journal of Scheduling, 12 (2009), 375-388.  doi: 10.1007/s10951-009-0103-2. [8] V. Caraffa, S. Ianes, T. P. Bagchi and C. Sriskandarajah, Minimizing makespan in a blocking flowshop using genetic algorithms, International Journal of Production Economics, 70 (2001), 101-115.  doi: 10.1016/S0925-5273(99)00104-8. [9] A. Che, V. Kats and E. Levner, An efficient bicriteria algorithm for stable robotic flow shop scheduling, European Journal of Operational Research, 260 (2017), 964-971.  doi: 10.1016/j.ejor.2017.01.033. [10] T. C. E. Cheng, B. Peng and Z. Lü, A hybrid evolutionary algorithm to solve the job shop scheduling problem, Annals of Operations Research, 242 (2016), 223-237.  doi: 10.1007/s10479-013-1332-5. [11] D. Cinar, J. A. Oliveira, Y. I. Topcu and P. M. Pardalos, A priority-based genetic algorithm for a flexible job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 1391-1415.  doi: 10.3934/jimo.2016.12.1391. [12] A. D'Ariano, D. Pacciarelli and M. Pistelli, A branch and bound algorithm for scheduling trains in a railway network, European Journal of Operational Research, 183 (2007), 643-657.  doi: 10.1016/j.ejor.2006.10.034. [13] A. D'Ariano, D. Pacciarelli and M. Pistelli, Real-time scheduling of aircraft arrivals and departures in a terminal maneuvering area, Networks, 65 (2015), 212-227.  doi: 10.1002/net.21599. [14] B. Q. Fan and T. C. E. Cheng, Two-agent scheduling in a flowshop, European Journal of Operational Research, 252 (2016), 376-384.  doi: 10.1016/j.ejor.2016.01.009. [15] J. Grabowski and J. Pempera, The permutation flow shop problem with blocking. A tabu search approach, Omega, 35 (2007), 302-311.  doi: 10.1016/j.omega.2005.07.004. [16] H. Gröflin and A. Klinkert, A new neighborhood and tabu search for the Blocking Job Shop, Discrete Applied Mathematics, 157 (2009), 3646-3655.  doi: 10.1016/j.dam.2009.02.020. [17] E. Kozan and S. Q. Liu, A demand-responsive decision support system for coal transportation, Decision Support Systems, 54 (2012), 665-680.  doi: 10.1016/j.dss.2012.08.012. [18] E. Kozan and S. Q. Liu, An operational-level multi-stage mine production timetabling model for optimally synchronising drilling, blasting and excavating operations, International Journal of Mining Reclamation and Environment, 31 (2017), 457-474.  doi: 10.1080/17480930.2016.1160818. [19] E. Kozan and S. Q. Liu, A new open-pit multi-stage mine production timetabling model for drilling, blasting and excavating operations, Mining Technology, 125 (2016), 47-53. [20] J. Lange and F. Werner, Approaches to modeling train scheduling problems as job-shop problems with blocking constraints, Journal of Scheduling, 21 (2018), 191-207.  doi: 10.1007/s10951-017-0526-0. [21] J. Y. T. Leung, L. Kelly and J. H. Anderson, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, USA, 2004. [22] Y. K. Lin and C. S. Chong, A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 703-717. [23] S. Q. Liu and E. Kozan, Parallel-identical-machine job-shop scheduling with different stage-dependent buffering requirements, Computers and Operations Research, 74 (2016), 31-41.  doi: 10.1016/j.cor.2016.04.023. [24] S. Q. Liu and E. Kozan, Optimising a coal rail network under capacity constraints, Flexible Services and Manufacturing Journal, 23 (2011), 90-110.  doi: 10.1007/s10696-010-9069-9. [25] S. Q. Liu and E. Kozan, Integration of mathematical models for ore mining industry, International Journal of Systems Science: Operations and Logistics, (2017), 1-14.  doi: 10.1080/23302674.2017.1344330. [26] S. Q. Liu and E. Kozan, Scheduling a flow shop with combined buffer conditions, International Journal of Production Economics, 117 (2009), 371-380.  doi: 10.1016/j.ijpe.2008.11.007. [27] S. Q. Liu and E. Kozan, A hybrid metaheuristic algorithm to optimise a real-world robotic cell, Computers and Operations Research, 84 (2017), 188-194.  doi: 10.1016/j.cor.2016.09.011. [28] S. Q. Liu, E. Kozan, Y. Zhang and F. T. S. Chan, Job shop scheduling with a combination of four buffering constraints, International Journal of Production Research, (2017), 1-20. [29] S. Q. Liu and E. Kozan, Scheduling trains with priorities: a no-wait blocking parallel-machine job-shop scheduling model, Transportation Science, 45 (2011), 175-198.  doi: 10.1007/s10696-010-9069-9. [30] S. Q. Liu and E. Kozan, Scheduling a flow shop with combined buffer conditions, International Journal of Production Economics, 117 (2009), 371-380.  doi: 10.1016/j.ijpe.2008.11.007. [31] S. Q. Liu and E. Kozan, Scheduling trains as a blocking parallel-machine job shop scheduling problem, Computers and Operations Research, 36 (2009), 2840-2852.  doi: 10.1016/j.cor.2008.12.012. [32] S. Q. Liu and H. L. Ong, Metaheuristics for the mixed shop scheduling problem, Asia-Pacific Journal of Operational Research, 21 (2004), 97-115.  doi: 10.1142/S0217595904000072. [33] S. Q. Liu and H. L. Ong, A comparative study of algorithms for the flowshop scheduling problem, Asia-Pacific Journal of Operational Research, 19 (2002), 205-222. [34] A. Mascis and D. Pacciarelli, Job-shop scheduling with blocking and no-wait constraints, European Journal of Operational Research, 143 (2002), 498-517.  doi: 10.1016/S0377-2217(01)00338-1. [35] M. Masoud, E. Kozan, G. Kent and S. Q. Liu, Experimental dataset for optimising the freight rail operations, Data in Brief, 9 (2016), 492-500.  doi: 10.1016/j.dib.2016.09.015. [36] M. Masoud, G. Kent, E. Kozan and S. Q. Liu, A new multi-objective model to optimize rail transport scheduler, Journal of Transportation Technologies, 6 (2016), 86-98. [37] M. Masoud, E. Kozan, G. Kent and S. Q. Liu, A new constraint programming approach for optimising a coal rail system, Optimization Letters, 11 (2017), 725-738.  doi: 10.1007/s11590-016-1041-5. [38] M. Masoud, E. Kozan, G. Kent and S. Q. Liu, An integrated approach to optimise sugarcane rail operations, Computers and Industrial Engineering, 98 (2016), 211-220.  doi: 10.1016/j.cie.2016.06.002. [39] S. T. McCormick, M. L. Pinedo, S. Shenker and B. Wolf, Sequencing in an assembly line with blocking to minimize cycle time, Operations Research, 37 (1989), 925-935.  doi: 10.1287/opre.37.6.925. [40] E. Mokotoff, Algorithms for bicriteria minimization in the permutation flow shop scheduling problem, Journal of Industrial and Management Optimization, 7 (2011), 253-282.  doi: 10.3934/jimo.2011.7.253. [41] M. Nawaz and E. E. Enscore, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11 (1983), 91-95.  doi: 10.1016/0305-0483(83)90088-9. [42] D.-N. Pham and A. Klinkert, Surgical case scheduling as a generalized job shop scheduling problem, European Journal of Operational Research, 185 (2008), 1011-1025.  doi: 10.1016/j.ejor.2006.03.059. [43] M. L. Pinedo, Planning and Scheduling in Manufacturing and Services, Springer, New York, USA, 2005. doi: 10.1007/b139030. [44] C. N. Potts, D. B. Shmoys and D. P. Williamson, Permutation vs. non-permutation flow shop schedules, Operations Research Letters, 10 (1991), 281-284.  doi: 10.1016/0167-6377(91)90014-G. [45] M. Pranzo and D. Pacciarelli, An iterated greedy metaheuristic for the blocking job shop scheduling problem, Journal of Heuristics, 22 (2016), 587-611.  doi: 10.1007/s10732-014-9279-5. [46] D. P. Ronconi, A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking, Annals of Operations Research, 138 (2005), 53-65.  doi: 10.1007/s10479-005-2444-3. [47] D. P. Ronconi, A note on constructive heuristics for the flowshop problem with blocking, International Journal of Production Economics, 87 (2004), 39-48.  doi: 10.1016/S0925-5273(03)00065-3. [48] B. Roy and B. Sussmann, Les Problèmes D'ordonnancement avec Contraintes Disjonctives, Note DS No, Montrouge, 1964. [49] M. Samà, A. D'Ariano, P. D'Ariano and D. Pacciarelli, Scheduling models for optimal aircraft traffic control at busy airports: Tardiness, priorities, equity and violations considerations, Omega, 67 (2017), 81-98.  doi: 10.1016/j.omega.2016.04.003. [50] Y. W. Shin and D. H. Moon, Throughput of flow lines with unreliable parallel-machine workstations and blocking, Journal of Industrial and Management Optimization, 13 (2017), 901-916. [51] J. K. Winch, X. Cai and G. L. Vairaktarakis, Cyclic job scheduling in paced assembly lines with cross-trained workers, International journal of production research, 45 (2007), 803-828. [52] P. Yan, A. Che, E. Levner and S. Q. Liu, A heuristic for inserting randomly arriving jobs into an existing hoist schedule, IEEE Transactions on Automation Science and Engineering, (2017), 1-8.  doi: 10.1109/TASE.2017.2749429. [53] P. Yan, A. Che, N. Yang and C. Chu, A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem, International Journal of Production Research, 50 (2012), 6403-6418. [54] P. Yan, C. Chu, N. Yang and A. Che, A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows, International Journal of Production Research, 48 (2010), 6461-6480. [55] P. Yan, A. Che, X. Cai and X. Tang, Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance, Computers and Operations Research, 50 (2014), 128-140.  doi: 10.1016/j.cor.2014.04.002.

show all references

References:
 [1] I. N. K. Abadi, N. G. Hall and C. Sriskandarajah, Minimizing cycle time in a blocking flowshop, Oper. Res., 48 (2000), 177-180.  doi: 10.1287/opre.48.1.177.12451. [2] D. Bai, M Tang, Z. H. Zhang and E. D. R. Santibanez-Gonzalez, Flow shop learning effect scheduling problem with release dates, Omega, (2017).  doi: 10.1016/j.omega.2017.10.002. [3] K. R. Baker and T. Dan, Principles of Sequencing and Scheduling, Wiley Publishing, 2009. doi: 10.1002/9780470451793. [4] P. Brucker and T. Kampmeyer, Cyclic job shop scheduling problems with blocking, Annals of Operations Research, 159 (2008), 161-181.  doi: 10.1007/s10479-007-0276-z. [5] R. L. Burdett and E. Kozan, An integrated approach for scheduling health care activities in a hospital, European Journal of Operational Research, 264 (2018), 756-773.  doi: 10.1016/j.ejor.2017.06.051. [6] X. Cai, X. Wu and X. Zhou, Optimal Stochastic Scheduling, Springer, CA, USA, 2014. doi: 10.1007/978-1-4899-7405-1. [7] X. Cai, X. Wu and X. Zhou, Stochastic scheduling on parallel machines to minimize discounted holding costs, Journal of Scheduling, 12 (2009), 375-388.  doi: 10.1007/s10951-009-0103-2. [8] V. Caraffa, S. Ianes, T. P. Bagchi and C. Sriskandarajah, Minimizing makespan in a blocking flowshop using genetic algorithms, International Journal of Production Economics, 70 (2001), 101-115.  doi: 10.1016/S0925-5273(99)00104-8. [9] A. Che, V. Kats and E. Levner, An efficient bicriteria algorithm for stable robotic flow shop scheduling, European Journal of Operational Research, 260 (2017), 964-971.  doi: 10.1016/j.ejor.2017.01.033. [10] T. C. E. Cheng, B. Peng and Z. Lü, A hybrid evolutionary algorithm to solve the job shop scheduling problem, Annals of Operations Research, 242 (2016), 223-237.  doi: 10.1007/s10479-013-1332-5. [11] D. Cinar, J. A. Oliveira, Y. I. Topcu and P. M. Pardalos, A priority-based genetic algorithm for a flexible job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 1391-1415.  doi: 10.3934/jimo.2016.12.1391. [12] A. D'Ariano, D. Pacciarelli and M. Pistelli, A branch and bound algorithm for scheduling trains in a railway network, European Journal of Operational Research, 183 (2007), 643-657.  doi: 10.1016/j.ejor.2006.10.034. [13] A. D'Ariano, D. Pacciarelli and M. Pistelli, Real-time scheduling of aircraft arrivals and departures in a terminal maneuvering area, Networks, 65 (2015), 212-227.  doi: 10.1002/net.21599. [14] B. Q. Fan and T. C. E. Cheng, Two-agent scheduling in a flowshop, European Journal of Operational Research, 252 (2016), 376-384.  doi: 10.1016/j.ejor.2016.01.009. [15] J. Grabowski and J. Pempera, The permutation flow shop problem with blocking. A tabu search approach, Omega, 35 (2007), 302-311.  doi: 10.1016/j.omega.2005.07.004. [16] H. Gröflin and A. Klinkert, A new neighborhood and tabu search for the Blocking Job Shop, Discrete Applied Mathematics, 157 (2009), 3646-3655.  doi: 10.1016/j.dam.2009.02.020. [17] E. Kozan and S. Q. Liu, A demand-responsive decision support system for coal transportation, Decision Support Systems, 54 (2012), 665-680.  doi: 10.1016/j.dss.2012.08.012. [18] E. Kozan and S. Q. Liu, An operational-level multi-stage mine production timetabling model for optimally synchronising drilling, blasting and excavating operations, International Journal of Mining Reclamation and Environment, 31 (2017), 457-474.  doi: 10.1080/17480930.2016.1160818. [19] E. Kozan and S. Q. Liu, A new open-pit multi-stage mine production timetabling model for drilling, blasting and excavating operations, Mining Technology, 125 (2016), 47-53. [20] J. Lange and F. Werner, Approaches to modeling train scheduling problems as job-shop problems with blocking constraints, Journal of Scheduling, 21 (2018), 191-207.  doi: 10.1007/s10951-017-0526-0. [21] J. Y. T. Leung, L. Kelly and J. H. Anderson, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, USA, 2004. [22] Y. K. Lin and C. S. Chong, A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 703-717. [23] S. Q. Liu and E. Kozan, Parallel-identical-machine job-shop scheduling with different stage-dependent buffering requirements, Computers and Operations Research, 74 (2016), 31-41.  doi: 10.1016/j.cor.2016.04.023. [24] S. Q. Liu and E. Kozan, Optimising a coal rail network under capacity constraints, Flexible Services and Manufacturing Journal, 23 (2011), 90-110.  doi: 10.1007/s10696-010-9069-9. [25] S. Q. Liu and E. Kozan, Integration of mathematical models for ore mining industry, International Journal of Systems Science: Operations and Logistics, (2017), 1-14.  doi: 10.1080/23302674.2017.1344330. [26] S. Q. Liu and E. Kozan, Scheduling a flow shop with combined buffer conditions, International Journal of Production Economics, 117 (2009), 371-380.  doi: 10.1016/j.ijpe.2008.11.007. [27] S. Q. Liu and E. Kozan, A hybrid metaheuristic algorithm to optimise a real-world robotic cell, Computers and Operations Research, 84 (2017), 188-194.  doi: 10.1016/j.cor.2016.09.011. [28] S. Q. Liu, E. Kozan, Y. Zhang and F. T. S. Chan, Job shop scheduling with a combination of four buffering constraints, International Journal of Production Research, (2017), 1-20. [29] S. Q. Liu and E. Kozan, Scheduling trains with priorities: a no-wait blocking parallel-machine job-shop scheduling model, Transportation Science, 45 (2011), 175-198.  doi: 10.1007/s10696-010-9069-9. [30] S. Q. Liu and E. Kozan, Scheduling a flow shop with combined buffer conditions, International Journal of Production Economics, 117 (2009), 371-380.  doi: 10.1016/j.ijpe.2008.11.007. [31] S. Q. Liu and E. Kozan, Scheduling trains as a blocking parallel-machine job shop scheduling problem, Computers and Operations Research, 36 (2009), 2840-2852.  doi: 10.1016/j.cor.2008.12.012. [32] S. Q. Liu and H. L. Ong, Metaheuristics for the mixed shop scheduling problem, Asia-Pacific Journal of Operational Research, 21 (2004), 97-115.  doi: 10.1142/S0217595904000072. [33] S. Q. Liu and H. L. Ong, A comparative study of algorithms for the flowshop scheduling problem, Asia-Pacific Journal of Operational Research, 19 (2002), 205-222. [34] A. Mascis and D. Pacciarelli, Job-shop scheduling with blocking and no-wait constraints, European Journal of Operational Research, 143 (2002), 498-517.  doi: 10.1016/S0377-2217(01)00338-1. [35] M. Masoud, E. Kozan, G. Kent and S. Q. Liu, Experimental dataset for optimising the freight rail operations, Data in Brief, 9 (2016), 492-500.  doi: 10.1016/j.dib.2016.09.015. [36] M. Masoud, G. Kent, E. Kozan and S. Q. Liu, A new multi-objective model to optimize rail transport scheduler, Journal of Transportation Technologies, 6 (2016), 86-98. [37] M. Masoud, E. Kozan, G. Kent and S. Q. Liu, A new constraint programming approach for optimising a coal rail system, Optimization Letters, 11 (2017), 725-738.  doi: 10.1007/s11590-016-1041-5. [38] M. Masoud, E. Kozan, G. Kent and S. Q. Liu, An integrated approach to optimise sugarcane rail operations, Computers and Industrial Engineering, 98 (2016), 211-220.  doi: 10.1016/j.cie.2016.06.002. [39] S. T. McCormick, M. L. Pinedo, S. Shenker and B. Wolf, Sequencing in an assembly line with blocking to minimize cycle time, Operations Research, 37 (1989), 925-935.  doi: 10.1287/opre.37.6.925. [40] E. Mokotoff, Algorithms for bicriteria minimization in the permutation flow shop scheduling problem, Journal of Industrial and Management Optimization, 7 (2011), 253-282.  doi: 10.3934/jimo.2011.7.253. [41] M. Nawaz and E. E. Enscore, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11 (1983), 91-95.  doi: 10.1016/0305-0483(83)90088-9. [42] D.-N. Pham and A. Klinkert, Surgical case scheduling as a generalized job shop scheduling problem, European Journal of Operational Research, 185 (2008), 1011-1025.  doi: 10.1016/j.ejor.2006.03.059. [43] M. L. Pinedo, Planning and Scheduling in Manufacturing and Services, Springer, New York, USA, 2005. doi: 10.1007/b139030. [44] C. N. Potts, D. B. Shmoys and D. P. Williamson, Permutation vs. non-permutation flow shop schedules, Operations Research Letters, 10 (1991), 281-284.  doi: 10.1016/0167-6377(91)90014-G. [45] M. Pranzo and D. Pacciarelli, An iterated greedy metaheuristic for the blocking job shop scheduling problem, Journal of Heuristics, 22 (2016), 587-611.  doi: 10.1007/s10732-014-9279-5. [46] D. P. Ronconi, A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking, Annals of Operations Research, 138 (2005), 53-65.  doi: 10.1007/s10479-005-2444-3. [47] D. P. Ronconi, A note on constructive heuristics for the flowshop problem with blocking, International Journal of Production Economics, 87 (2004), 39-48.  doi: 10.1016/S0925-5273(03)00065-3. [48] B. Roy and B. Sussmann, Les Problèmes D'ordonnancement avec Contraintes Disjonctives, Note DS No, Montrouge, 1964. [49] M. Samà, A. D'Ariano, P. D'Ariano and D. Pacciarelli, Scheduling models for optimal aircraft traffic control at busy airports: Tardiness, priorities, equity and violations considerations, Omega, 67 (2017), 81-98.  doi: 10.1016/j.omega.2016.04.003. [50] Y. W. Shin and D. H. Moon, Throughput of flow lines with unreliable parallel-machine workstations and blocking, Journal of Industrial and Management Optimization, 13 (2017), 901-916. [51] J. K. Winch, X. Cai and G. L. Vairaktarakis, Cyclic job scheduling in paced assembly lines with cross-trained workers, International journal of production research, 45 (2007), 803-828. [52] P. Yan, A. Che, E. Levner and S. Q. Liu, A heuristic for inserting randomly arriving jobs into an existing hoist schedule, IEEE Transactions on Automation Science and Engineering, (2017), 1-8.  doi: 10.1109/TASE.2017.2749429. [53] P. Yan, A. Che, N. Yang and C. Chu, A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem, International Journal of Production Research, 50 (2012), 6403-6418. [54] P. Yan, C. Chu, N. Yang and A. Che, A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows, International Journal of Production Research, 48 (2010), 6461-6480. [55] P. Yan, A. Che, X. Cai and X. Tang, Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance, Computers and Operations Research, 50 (2014), 128-140.  doi: 10.1016/j.cor.2014.04.002.
Blocking conditions on a pair of operations processed on the same machine
The result of a three-machine four-job BPFSS instance, obtained by the proposed alternative-graph-based constructive algorithm
The result of a three-machine four-job BPFSS instance, obtained by the directed-graph-based constructive algorithm
A directed alternative graph for a feasible BJSS schedule
A cyclic directed alternative graph for an infeasible BGFSS schedule
A cyclic directed alternative graph for an infeasible BGFSS schedule
The processing times of four jobs in a numerical example
 M1 M2 M3 J1 p1=1 p5=3 p9=3 J2 p2=1 p6=2 p10=2 J3 p3=4 p7=1 p11=4 J4 p4=2 p8=2 p12=2
 M1 M2 M3 J1 p1=1 p5=3 p9=3 J2 p2=1 p6=2 p10=2 J3 p3=4 p7=1 p11=4 J4 p4=2 p8=2 p12=2
 [1] Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial and Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11 [2] Sun-Ho Choi, Hyowon Seo, Minha Yoo. A multi-stage SIR model for rumor spreading. Discrete and Continuous Dynamical Systems - B, 2020, 25 (6) : 2351-2372. doi: 10.3934/dcdsb.2020124 [3] Li Deng, Wenjie Bi, Haiying Liu, Kok Lay Teo. A multi-stage method for joint pricing and inventory model with promotion constrains. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1653-1682. doi: 10.3934/dcdss.2020097 [4] Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial and Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109 [5] Jinghuan Li, Yu Li, Shuhua Zhang. Optimal expansion timing decisions in multi-stage PPP projects involving dedicated asset and government subsidies. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2065-2086. doi: 10.3934/jimo.2019043 [6] Jinghuan Li, Shuhua Zhang, Yu Li. Modelling and computation of optimal multiple investment timing in multi-stage capacity expansion infrastructure projects. Journal of Industrial and Management Optimization, 2022, 18 (1) : 297-314. doi: 10.3934/jimo.2020154 [7] Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial and Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140 [8] Ruijun Zhao, Jemal Mohammed-Awel. A mathematical model studying mosquito-stage transmission-blocking vaccines. Mathematical Biosciences & Engineering, 2014, 11 (5) : 1229-1245. doi: 10.3934/mbe.2014.11.1229 [9] Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021151 [10] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [11] Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029 [12] Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1289-1314. doi: 10.3934/jimo.2020022 [13] Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial and Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185 [14] Chunmei Zhang, Wenxue Li, Ke Wang. Graph-theoretic approach to stability of multi-group models with dispersal. Discrete and Continuous Dynamical Systems - B, 2015, 20 (1) : 259-280. doi: 10.3934/dcdsb.2015.20.259 [15] Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391 [16] Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial and Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024 [17] Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete and Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253 [18] Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 [19] Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 [20] Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088

2021 Impact Factor: 1.411