The stage shop scheduling problem: lower bound and metaheuristic

Document Type : Article

Authors

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

Abstract

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.

Keywords

Main Subjects

References

References:
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 (2000).
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.,  Ozbakir, L., and Yavuz, Y. "Mathematical models for job-shop scheduling problems with routing and process plan flexibility", 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  flexible job shops with multiple process plans", International Journal of Production Research, 51(12), pp. 3748-3764 (2013).
11. Nasiri, M.M. "A modified 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  flexible 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 effective 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).
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,  flow and job shops", Oper. Res., 29(3), pp. 511-522 (1981).
21. Nasiri, M.M. "A pseudo particle swarm optimization for the RCPSP", The International Journal of Advanced Manufacturing Technology, 65, pp. 909-918 (2013).
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 permutation  flow 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 (2011).
27. Yang, X.-S., Nature-Inspired Metaheuristic Algorithms, Luniver Press (2010).
28. Khadwilard, A., Chansombat, S., Thepphakorn, T., et al. "Application of fire 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 fire 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. "Fire 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 flow and inflation: 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. Garcia, 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 (2009).
37. Zar, J., Biostatistical analysis, 4th Edition, Prentice Hall, Englewood Cliffs (1999).
Scientia Iranica
Volume 27, Issue 2
Transactions on Industrial Engineering (E)
March and April 2020
Pages 862-879

Files

Share

How to cite

Statistics