• Previous Article
    A new relaxed CQ algorithm for solving split feasibility problems in Hilbert spaces and its applications
  • JIMO Home
  • This Issue
  • Next Article
    Partially symmetric nonnegative rectangular tensors and copositive rectangular tensors
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, 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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'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.

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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'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.

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

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

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

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

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

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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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, 2018, 0 (0) : 1233-1249. doi: 10.3934/dcdss.2019085

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007

[19]

Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial & Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076

[20]

Fan Zhang, Guifa Teng, Mengmeng Gao, Shuai Zhang, Jingjing Zhang. Multi-machine and multi-task emergency allocation algorithm based on precedence rules. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1501-1513. doi: 10.3934/dcdss.2019103

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (32)
  • HTML views (564)
  • Cited by (0)

[Back to Top]