• 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]

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

[2]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[3]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[4]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228

[5]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931

[6]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (365)
  • HTML views (1768)
  • Cited by (1)

[Back to Top]