The stage shop scheduling problem: lower bound and metaheuristic

Document Type : Article


School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran


Remarkable efforts are made to develop the job shop scheduling problem up to now. As a novel generalization, the stage shop can be defined as an environment, in which each job is composed of some stages and each stage may include one operation or more. A stage can be defined a subset of operations of a job, such that these operations can be done in any arbitrary relative order while the stages should be processed in a predetermined order. In other words, the operations of a stage cannot be initiated until all operations of the prior stage are completed. In this paper, an innovative lower bound based on solving the preemptive open shop (using a linear programming model in polynomial time) is devised for the makespan in a stage shop problem. In addition, three metaheuristics, including firefly, harmony search and water wave optimization algorithms are applied to the problem. The results of the algorithms are compared with each other, the proposed lower bound, and a commercial solver.


Main Subjects

1. Nasiri, M.M., Yazdanparast, R., and Jolai, F. A simulation
optimisation approach for real-time scheduling
in an open shop environment using a composite
dispatching rule", International Journal of Computer
Integrated Manufacturing., 30(12), pp. 1239{
1252 (2017).
2. Lange, J. and Werner, F. Approaches to modeling
train scheduling problems as job-shop problems with
blocking constraints", Journal of Scheduling., 21(2),
pp. 191{207 (2018).
3. Shakhlevich, N.V., Sotskov, Y.N., and Werner, F.
Complexity of mixed shop scheduling problems: A
survey", Eur. J. Oper. Res., 120(2), pp. 343{351
4. Ramudhin, A. and Marier, P. The generalized shifting
bottleneck procedure", Eur. J. Oper. Res., 93(1), pp.
34{48 (1996).
5. Kis, T. Job-shop scheduling with processing alternatives",
Eur. J. Oper. Res., 151(2), pp. 307{332 (2003).
6. Ozguven, C.,  Ozbakr, L., and Yavuz, Y. Mathematical
models for job-shop scheduling problems with
routing and process plan
exibility", Appl. Math.
Modell., 34(6), pp. 1539{1548 (2010).
7. Nasiri, M.M. and Kianfar, F. A hybrid scatter
search for the partial job shop scheduling problem",
The International Journal of Advanced Manufacturing
Technology, 52(9{12), pp. 1031{1038 (2011).
8. Nasiri, M.M. and Kianfar, F. A GA/TS algorithm
for the stage shop scheduling problem", Comput. Ind.
Eng., 61(1), pp. 161{170 (2011).
9. Dugarzhapov, A. and Kononov, A. A polynomialtime
algorithm for the preemptive mixed-shop problem
with two unit operations per job", Journal of Scheduling,
19(1), pp. 61{72 (2016).
10. Doh, H.-H., Yu, J.-M., Kim, J.-S., et al. A priority
scheduling approach for
exible job shops with multiple
process plans", International Journal of Production
Research, 51(12), pp. 3748{3764 (2013).
11. Nasiri, M.M. A modi ed ABC algorithm for the stage
shop scheduling problem", Applied Soft Computing,
28, pp. 81{89 (2015).
12. Rossi, A., Soldani, S., and Lanzetta, M. Hybrid stage
shop scheduling", Expert Systems with Applications,
42(8), pp. 4105{4119 (2015).
13. Jin, L., Tang, Q., Zhang, C., et al. More MILP models
for integrated process planning and scheduling", International
Journal of Production Research, 54(14) pp.
1{16 (2016).
14. Gao, K.-Z., Suganthan, P.N., Pan, Q.-K., et al.
Discrete harmony search algorithm for
exible job
shop scheduling problem with multiple objectives",
Journal of Intelligent Manufacturing, 27(2), pp. 363{
374 (2016).
15. Bo_zek, A. and Werner, F. Flexible job shop scheduling
with lot streaming and sublot size optimisation",
International Journal of Production Research, 56(19),
pp. 1{21 (2017).
16. Zubaran, T.K. and Ritt, M. An e ective heuristic
algorithm for the partial shop scheduling problem",
Comput. Oper. Res., 93, pp. 51{65 (2018).
17. Carlier, J. The one-machine sequencing problem",
Eur. J. Oper. Res., 11(1), pp. 42{47 (1982).
M.M. Nasiri and M. Hamid/Scientia Iranica, Transactions E: Industrial Engineering 27 (2020) 862{879 877
18. Nowicki, E. and Smutnicki, C. An advanced tabu
search algorithm for the job shop problem", Journal
of Scheduling, 8(2), pp. 145{159 (2005).
19. Pinedo, M., Scheduling: Theory, Algorithms, and
Systems, Springer (2012).
20. Cho, Y. and Sahni, S. Preemptive scheduling of
independent jobs with release and due times on open,

ow and job shops", Oper. Res., 29(3), pp. 511{522
21. Nasiri, M.M. A pseudo particle swarm optimization
for the RCPSP", The International Journal of Advanced
Manufacturing Technology, 65, pp. 909{918
22. Saka, M.P., Hasancebi, O., and Geem, Z.W. Metaheuristics
in structural optimization and discussions on
harmony search algorithm", Swarm and Evolutionary
Computation, 28, pp. 88{97 (2016).
23. Geem, Z.W., Kim, J.H., and Loganathan, G. A new
heuristic optimization algorithm: harmony search",
Simulation, 76(2), pp. 60{68 (2001).
24. Omran, M.G. and Mahdavi, M. Global-best harmony
search", Applied Mathematics and Computation,
198(2), pp. 643{656 (2008).
25. Wang, L., Pan, Q.-K., and Tasgetiren, M.F. A
hybrid harmony search algorithm for the blocking
ow shop scheduling problem", Comput.
Ind. Eng., 61(1), pp. 76{83 (2011).
26. Das, S., Mukhopadhyay, A., Roy, A., et al. Exploratory
power of the harmony search algorithm:
analysis and improvements for global numerical optimization",
Systems, Man, and Cybernetics, Part B:
Cybernetics, IEEE Transactions on, 41(1), pp. 89{106
27. Yang, X.-S., Nature-Inspired Metaheuristic Algorithms,
Luniver Press (2010).
28. Khadwilard, A., Chansombat, S., Thepphakorn, T., et
al. Application of re
y algorithm and its parameter
setting for job shop scheduling", in First Symposium
on Hands-On Research and Development (2011).
29. Chandrasekaran, K. and Simon, S.P. Network and
reliability constrained unit commitment problem using
binary real coded re
y algorithm", International
Journal of Electrical Power & Energy Systems, 43(1),
pp. 921{932 (2012).
30. Gandomi, A., Yang, X.-S., Talatahari, S., et al.
y algorithm with chaos", Communications in
Nonlinear Science and Numerical Simulation, 18(1),
pp. 89{98 (2013).
31. Zheng, Y.-J. Water wave optimization: a new natureinspired
metaheuristic", Comput. Oper. Res., 55, pp.
1{11 (2015).
32. Taillard, E.D. Available from: <http://mistic.heigvd.
ch/taillard> (2017).
33. Taillard, E.D. Benchmarks for basic scheduling problems",
Eur. J. Oper. Res., 64(2), pp. 278{285 (1993).
34. Mousavi, S.M., Hajipour, V., Niaki, S.T.A., et al.
Optimizing multi-item multi-period inventory control
system with discounted cash
ow and in
ation: Two
calibrated meta-heuristic algorithms", Appl. Math.
Modell., 37(4), pp. 2241{2256 (2013).
35. Peace, G.S., Taguchi Methods: A Hands-on Approach,
Addison Wesley Publishing Company (1993).
36. Garca, S., Molina, D., Lozano, M., et al. A study
on the use of non-parametric tests for analyzing the
evolutionary algorithms' behaviour: a case study on
the CEC'2005 special session on real parameter optimization",
Journal of Heuristics, 15(6), pp. 617{644
37. Zar, J., Biostatistical analysis, 4th Edition, Prentice
Hall, Englewood Cli s (1999).