• 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  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 & Management Optimization, 2019, 15 (1) : 221-233. doi: 10.3934/jimo.2018040
References:
[1]

I. N. K. AbadiN. 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.  Google Scholar

[2]

D. BaiM TangZ. 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.  Google Scholar

[3]

K. R. Baker and T. Dan, Principles of Sequencing and Scheduling, Wiley Publishing, 2009. doi: 10.1002/9780470451793.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

X. Cai, X. Wu and X. Zhou, Optimal Stochastic Scheduling, Springer, CA, USA, 2014. doi: 10.1007/978-1-4899-7405-1.  Google Scholar

[7]

X. CaiX. 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.  Google Scholar

[8]

V. CaraffaS. IanesT. 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.  Google Scholar

[9]

A. CheV. 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.  Google Scholar

[10]

T. C. E. ChengB. 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.  Google Scholar

[11]

D. CinarJ. A. OliveiraY. 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.  Google Scholar

[12]

A. D'ArianoD. 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.  Google Scholar

[13]

A. D'ArianoD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[21]

J. Y. T. Leung, L. Kelly and J. H. Anderson, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, USA, 2004.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

S. Q. LiuE. KozanY. Zhang and F. T. S. Chan, Job shop scheduling with a combination of four buffering constraints, International Journal of Production Research, (2017), 1-20.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[35]

M. MasoudE. KozanG. 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.  Google Scholar

[36]

M. MasoudG. KentE. Kozan and S. Q. Liu, A new multi-objective model to optimize rail transport scheduler, Journal of Transportation Technologies, 6 (2016), 86-98.   Google Scholar

[37]

M. MasoudE. KozanG. 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.  Google Scholar

[38]

M. MasoudE. KozanG. 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.  Google Scholar

[39]

S. T. McCormickM. L. PinedoS. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[43]

M. L. Pinedo, Planning and Scheduling in Manufacturing and Services, Springer, New York, USA, 2005. doi: 10.1007/b139030.  Google Scholar

[44]

C. N. PottsD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[48]

B. Roy and B. Sussmann, Les Problèmes D'ordonnancement avec Contraintes Disjonctives, Note DS No, Montrouge, 1964. Google Scholar

[49]

M. SamàA. D'ArianoP. 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.  Google Scholar

[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.   Google Scholar

[51]

J. K. WinchX. 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.   Google Scholar

[52]

P. YanA. CheE. 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.  Google Scholar

[53]

P. YanA. CheN. 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.   Google Scholar

[54]

P. YanC. ChuN. 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.   Google Scholar

[55]

P. YanA. CheX. 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.  Google Scholar

show all references

References:
[1]

I. N. K. AbadiN. 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.  Google Scholar

[2]

D. BaiM TangZ. 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.  Google Scholar

[3]

K. R. Baker and T. Dan, Principles of Sequencing and Scheduling, Wiley Publishing, 2009. doi: 10.1002/9780470451793.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

X. Cai, X. Wu and X. Zhou, Optimal Stochastic Scheduling, Springer, CA, USA, 2014. doi: 10.1007/978-1-4899-7405-1.  Google Scholar

[7]

X. CaiX. 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.  Google Scholar

[8]

V. CaraffaS. IanesT. 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.  Google Scholar

[9]

A. CheV. 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.  Google Scholar

[10]

T. C. E. ChengB. 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.  Google Scholar

[11]

D. CinarJ. A. OliveiraY. 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.  Google Scholar

[12]

A. D'ArianoD. 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.  Google Scholar

[13]

A. D'ArianoD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[21]

J. Y. T. Leung, L. Kelly and J. H. Anderson, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, USA, 2004.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

S. Q. LiuE. KozanY. Zhang and F. T. S. Chan, Job shop scheduling with a combination of four buffering constraints, International Journal of Production Research, (2017), 1-20.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[35]

M. MasoudE. KozanG. 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.  Google Scholar

[36]

M. MasoudG. KentE. Kozan and S. Q. Liu, A new multi-objective model to optimize rail transport scheduler, Journal of Transportation Technologies, 6 (2016), 86-98.   Google Scholar

[37]

M. MasoudE. KozanG. 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.  Google Scholar

[38]

M. MasoudE. KozanG. 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.  Google Scholar

[39]

S. T. McCormickM. L. PinedoS. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[43]

M. L. Pinedo, Planning and Scheduling in Manufacturing and Services, Springer, New York, USA, 2005. doi: 10.1007/b139030.  Google Scholar

[44]

C. N. PottsD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[48]

B. Roy and B. Sussmann, Les Problèmes D'ordonnancement avec Contraintes Disjonctives, Note DS No, Montrouge, 1964. Google Scholar

[49]

M. SamàA. D'ArianoP. 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.  Google Scholar

[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.   Google Scholar

[51]

J. K. WinchX. 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.   Google Scholar

[52]

P. YanA. CheE. 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.  Google Scholar

[53]

P. YanA. CheN. 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.   Google Scholar

[54]

P. YanC. ChuN. 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.   Google Scholar

[55]

P. YanA. CheX. 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.  Google Scholar

Figure 1.  Blocking conditions on a pair of operations processed on the same machine
Figure 2.  The result of a three-machine four-job BPFSS instance, obtained by the proposed alternative-graph-based constructive algorithm
Figure 3.  The result of a three-machine four-job BPFSS instance, obtained by the directed-graph-based constructive algorithm
Figure 4.  A directed alternative graph for a feasible BJSS schedule
Figure 5.  A cyclic directed alternative graph for an infeasible BGFSS schedule
Figure 6.  A cyclic directed alternative graph for an infeasible BGFSS schedule
Table 1.  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 & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11

[2]

Li Deng, Wenjie Bi, Haiying Liu, Kok Lay Teo. A multi-stage method for joint pricing and inventory model with promotion constrains. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020097

[3]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019109

[4]

Jinghuan Li, Yu Li, Shuhua Zhang. Optimal expansion timing decisions in multi-stage PPP projects involving dedicated asset and government subsidies. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2019043

[5]

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

[6]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[7]

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 & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[8]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185

[9]

Chunmei Zhang, Wenxue Li, Ke Wang. Graph-theoretic approach to stability of multi-group models with dispersal. Discrete & Continuous Dynamical Systems - B, 2015, 20 (1) : 259-280. doi: 10.3934/dcdsb.2015.20.259

[10]

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 & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[11]

Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253

[12]

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 & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024

[13]

Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667

[14]

Jiangchuan Fan, Xinyu Guo, Jianjun Du, Weiliang Wen, Xianju Lu, Brahmani Louiza. Analysis of the clustering fusion algorithm for multi-band color image. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1233-1249. doi: 10.3934/dcdss.2019085

[15]

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 & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[16]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[17]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[18]

Ling Lin, Dong He, Zhiyi Tan. Bounds on delay start LPT algorithm for scheduling on two identical machines in the $l_p$ norm. Journal of Industrial & Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817

[19]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[20]

Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007

2018 Impact Factor: 1.025

Article outline

Figures and Tables

[Back to Top]