A three-stage optimization algorithm for the stochastic parallel machine scheduling problem with adjustable production rates. (English) Zbl 1264.90098

Summary: We consider a parallel machine scheduling problem with random processing/setup times and adjustable production rates. The objective functions to be minimized consist of two parts; the first part is related with the due date performance (i.e., the tardiness of the jobs), while the second part is related with the setting of machine speeds. Therefore, the decision variables include both the production schedule (sequences of jobs) and the production rate of each machine. The optimization process, however, is significantly complicated by the stochastic factors in the manufacturing system. To address the difficulty, a simulation-based three-stage optimization framework is presented in this paper for high-quality robust solutions to the integrated scheduling problem. The first stage (crude optimization) is featured by the ordinal optimization theory, the second stage (finer optimization) is implemented with a metaheuristic called differential evolution, and the third stage (fine-tuning) is characterized by a perturbation-based local search. Finally, computational experiments are conducted to verify the effectiveness of the proposed approach. Sensitivity analysis and practical implications are also discussed.


90B36 Stochastic scheduling theory in operations research
Full Text: DOI


[1] L. Mönch, J. W. Fowler, S. Dauzère-Pérès, S. J. Mason, and O. Rose, “A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations,” Journal of Scheduling, vol. 14, no. 6, pp. 583-599, 2011. · Zbl 06255107
[2] R. Gokhale and M. Mathirajan, “Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing,” The International Journal of Advanced Manufacturing Technology, vol. 60, no. 9-12, pp. 1099-1110, 2012.
[3] S. Q. Liu and E. Kozan, “Scheduling trains with priorities: a no-wait blocking parallel-machine job-shop scheduling model,” Transportation Science, vol. 45, no. 2, pp. 175-198, 2011.
[4] C.-J. Liao, C.-M. Chen, and C.-H. Lin, “Minimizing makespan for two parallel machines with job limit on each availability interval,” Journal of the Operational Research Society, vol. 58, no. 7, pp. 938-947, 2007. · Zbl 1178.90156
[5] C. N. Potts and V. A. Strusevich, “Fifty years of scheduling: a survey of milestones,” Journal of the Operational Research Society, vol. 60, no. 1, pp. S41-S68, 2009. · Zbl 1168.90311
[6] D. Biskup, J. Herrmann, and J. N. D. Gupta, “Scheduling identical parallel machines to minimize total tardiness,” International Journal of Production Economics, vol. 115, no. 1, pp. 134-142, 2008.
[7] A. Jouglet and D. Savourey, “Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates,” Computers & Operations Research, vol. 38, no. 9, pp. 1259-1266, 2011. · Zbl 1208.90066
[8] S.-W. Lin, Z.-J. Lee, K.-C. Ying, and C.-C. Lu, “Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates,” Computers & Operations Research, vol. 38, no. 5, pp. 809-815, 2011. · Zbl 1202.90138
[9] A. J. Ruiz-Torres, F. J. López, and J. C. Ho, “Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs,” European Journal of Operational Research, vol. 179, no. 2, pp. 302-315, 2007. · Zbl 1180.90136
[10] J. Banks, J. S. Carson, B. L. Nelson, and D. M. Nicol, Discrete-Event System Simulation, Prentice Hall, Upper Saddle River, NJ, USA, 5th edition, 2009.
[11] P. Brucker, Scheduling Algorithms, Springer, Berlin, Germany, 5th edition, 2007. · Zbl 1126.90001
[12] E. Kozan and B. Casey, “Alternative algorithms for the optimization of a simulation model of a multimodal container terminal,” Journal of the Operational Research Society, vol. 58, no. 9, pp. 1203-1213, 2007. · Zbl 1192.90018
[13] K. Muthuraman and H. Zha, “Simulation-based portfolio optimization for large portfolios with transaction costs,” Mathematical Finance, vol. 18, no. 1, pp. 115-134, 2008. · Zbl 1138.91560
[14] G. Van Ryzin and G. Vulcano, “Simulation-based optimization of virtual nesting controls for network revenue management,” Operations Research, vol. 56, no. 4, pp. 865-880, 2008. · Zbl 1167.90357
[15] R. Pasupathy, “On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization,” Operations Research, vol. 58, no. 4, part 1, pp. 889-901, 2010. · Zbl 1228.90069
[16] D. Bertsimas, O. Nohadani, and K. M. Teo, “Robust optimization for unconstrained simulation-based problems,” Operations Research, vol. 58, no. 1, pp. 161-178, 2010. · Zbl 1226.90074
[17] A. K. Miranda and E. Del Castillo, “Robust parameter design optimization of simulation experiments using stochastic perturbation methods,” Journal of the Operational Research Society, vol. 62, no. 1, pp. 198-205, 2011.
[18] S. H. Melouk, B. B. Keskin, C. Armbrester, and M. Anderson, “A simulation optimization-based decision support tool for mitigating traffic congestion,” Journal of the Operational Research Society, vol. 62, no. 11, pp. 1971-1982, 2011.
[19] L. Napalkova and G. Merkuryeva, “Multi-objective stochastic simulation-based optimisation applied to supply chain planning,” Technological and Economic Development of Economy, vol. 18, no. 1, pp. 132-148, 2012.
[20] Y. Zhang, M. L. Puterman, M. Nelson, and D. Atkins, “A simulation optimization approach to long-term care capacity planning,” Operations Research, vol. 60, no. 2, pp. 249-261, 2012. · Zbl 1251.90411
[21] Y. C. Ho, R. S. Sreenivas, and P. Vakili, “Ordinal optimization of DEDS,” Discrete Event Dynamic Systems, vol. 2, no. 1, pp. 61-88, 1992. · Zbl 0754.60133
[22] R. Storn and K. Price, “Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces,” Journal of Global Optimization, vol. 11, no. 4, pp. 341-359, 1997. · Zbl 0888.90135
[23] G. Onwubolu and D. Davendra, “Scheduling flow shops using differential evolution algorithm,” European Journal of Operational Research, vol. 171, no. 2, pp. 674-692, 2006. · Zbl 1090.90090
[24] L. Wang, Q.-K. Pan, P. N. Suganthan, W.-H. Wang, and Y.-M. Wang, “A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems,” Computers & Operations Research, vol. 37, no. 3, pp. 509-520, 2010. · Zbl 1175.90199
[25] Y.-C. Ho, Q.-C. Zhao, and Q.-S. Jia, Ordinal Optimization: Soft Optimization for Hard Problems, Springer, New York, NY, USA, 2007. · Zbl 1123.93007
[26] S.-C. Horng and S.-S. Lin, “An ordinal optimization theory-based algorithm for a class of simulation optimization problems and application,” Expert Systems with Applications, vol. 36, no. 5, pp. 9340-9349, 2009. · Zbl 05857016
[27] D. H. Wolpert and W. G. Macready, “No free lunch theorems for optimization,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67-82, 1997.
[28] C.-H. Chen, E. Yücesan, L. Dai, and H.-C. Chen, “Optimal budget allocation for discrete-event simulation experiments,” IIE Transactions, vol. 42, no. 1, pp. 60-70, 2010.
[29] R. Haupt, “A survey of priority rule-based scheduling,” Operations-Research-Spektrum, vol. 11, no. 1, pp. 3-16, 1989. · Zbl 0658.90047
[30] W. Y. Fowlkes, C. M. Creveling, and J. Derimiggio, Engineering Methods for Robust Product Design: Using Taguchi Methods in Technology and Product Development, Addison-Wesley, Reading, Mass, USA, 1995.
[31] B. Liu, L. Wang, and Y.-H. Jin, “Hybrid particle swarm optimization for flow shop scheduling with stochastic processing time,” in Computational Intelligence and Security, vol. 3801 of Lecture Notes in Computer Science, pp. 630-637, 2005.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.