Two-Level Robust Optimization for Uncertain Job Shop Scheduling Problem

Abstract:

This paper proposes a two-level robust optimization model in the context of job shop scheduling problem. The job shop scheduling problem optimizes the makespan under uncertain processing times, which are described by a set of scenarios. In the first-level optimization, a traditional stochastic optimization model is conducted to obtain the optimal expected performance as a standard performance, on which a concept of bad-scenario set is defined. In the second-level optimization, a robustness measure is given based on bad-scenario set. The objective function for the second robust optimization model is to combine expected performance and robustness measure. Finally, an extensive experiment was conducted to investigate the advantages of the proposed robust optimization model. The computational results show that the two-level model can achieve a better compromise between average performance and robustness than the existing robust optimization models.

• Periodical: Advanced Materials Research (Volume 1039)
• Pages: 514-521
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1039.514
• Online since: October 2014
• Authors: Bing Wang*, Xiao Yan Li, He Xia Meng
• Keywords: Bad Scenarios, Job Shop Scheduling, Robustness, Two-Level Robust Optimization

References

[1] Herroelen W, Leus R. Project scheduling under uncertainty: Survey and research potentials, European Journal of Operational Research, 2005, 165(2): 289-306.

DOI: 10.1016/j.ejor.2004.04.002

[2] Leon VJ, Wu SD, and Storer R H. Robustness measures and robust scheduling for job shops. IIE Transactions, 1994, 26(5): 32-43.

DOI: 10.1080/07408179408966626

[3] Kouvelis P, Yu D. Robust discrete optimization and its application. Kluwer Academic Publisher, (1997).

[4] Sabuncuoglu I, Goren S. Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research. International Journal of Computer Integrated Manufacturing 2009, 22: 138–57.

DOI: 10.1080/09511920802209033

[5] Wang B, Yang XF, and Li QY. Bad-scenario based robust scheduling model. Acta Automatica Sinica, 2012, 38(2): 275-283.

DOI: 10.3724/sp.j.1004.2012.00270

[6] Jensen MT. Generating robust and flexible job shop schedules using genetic algorithms. IEEE Transactions on Evolutionary Computation, 2003, 7(3): 275-288.

DOI: 10.1109/tevc.2003.810067

[7] Pinedo M. Minimizing the expected makespan in stochastic flow shops. Operations Research. 1982, 30: 148-162.

DOI: 10.1287/opre.30.1.148

[8] Assavapokee T, Realff MJ, Ammons JC, and Hong IH. Scenario relaxation algorithm for finite scenario-based min–max regret and min–max relative regret robust optimization. Computers & Operations Research, 2008, 35: 2093– 2102.

DOI: 10.1016/j.cor.2006.10.013

[9] Murvey JM, Vanderbei RJ, and Zenios SA. Robust optimization of large-scale systems. Operations Research, 1995, 43, 264-281.

DOI: 10.1287/opre.43.2.264

[10] Yamashita DS, Armentano VA, Laguna M. Robust optimization models for project scheduling with resource availability cost. Journal of Scheduling, 2007, 10: 67-76.

DOI: 10.1007/s10951-006-0326-4

[11] Daniels RL and Kouvelis P. Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 1995, 41: 363–376.

DOI: 10.1287/mnsc.41.2.363

[12] Kouvelis P, Daniels RL, Vairaktarakis G. Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Transactions, 2000, 32: 421-432.

DOI: 10.1080/07408170008963918

[13] Laguna M, Lino P, P´erez A, Quintanilla S, and Valls V. Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines. European Journal of Operational Research, 2000, 127(2), 444–457.

DOI: 10.1016/s0377-2217(99)00495-6

[14] Goren S., Sabuncuoglu I. and Koc U. Optimization of Schedule Stability and Efficiency under Processing Time Variability and Random Machine Breakdowns in a Job Shop Environment. Naval Research Logistics, 2012, 59(1): 26-38.

DOI: 10.1002/nav.20488

[15] Van Laarhoven PJM, Aarts EHL, Lenstra JK. Job shop scheduling by simulated annealing. Operations Research 1992, 40(1): 113–25.

DOI: 10.1287/opre.40.1.113

[16] He Z, Yang T, Tiger A. An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling. European Journal of Operational Research, 1996, 91(1): 99-117.

DOI: 10.1016/0377-2217(94)00361-0

[17] Steinhöfel K, Albrecht A, Wong C K. Two simulated annealing-based heuristics for the job shop scheduling problem. European Journal of Operational Research, 1999, 118(3): 524-548.

DOI: 10.1016/s0377-2217(98)00326-9

[18] Wang, L, Zheng, DZ. An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research, 2001, 28: 585–596.

DOI: 10.1016/s0305-0548(99)00137-9

[19] Nowicki E, Smutnicki C. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 1996, 42(6): 797-813.

DOI: 10.1287/mnsc.42.6.797

[20] Fisher H, Thompson GL. Probabilistic-learning combinations of local job-shop scheduling rules, in: J. Muth, G. Thompson (Eds. ). Industrial Scheduling, Prentice-Hall, Englewood Cliffs, NJ, (1963).

DOI: 10.21236/ad0600965

[21] Wang B, Yang X F, and Li Q Y. Genetic simulated-annealing algorithm for robust job shop scheduling. Fuzzy Information and Engineering, Vol. 2: Advances in Intelligent and Soft Computing, 2009, 62: 817-827.

DOI: 10.1007/978-3-642-03664-4_89