No Access

Simulation Optimization on Complex Job Shop Scheduling with Non-Identical Job Sizes

Lingxuan Liu

Department of Industrial Engineering & Management, Peking University, BJ 100871, P. R. China

E-mail Address: liulingxuan@pku.edu.cn

Corresponding author.

Search for more papers by this author

and

Leyuan Shi

Department of Industrial & Systems Engineering, University of Wisconsin-Madison, WI 53706, USA

E-mail Address: leyuan.shi@wisc.edu

Search for more papers by this author

https://doi.org/10.1142/S021759591950026XCited by:4 (Source: Crossref)

Abstract

This paper addresses the complex job shop scheduling problem with the consideration of non-identical job sizes. By simultaneously considering practical constraints of sequence dependent setup times, incompatible job families and job dependent batch processing time, we formulate this problem into a simulation optimization problem based on the disjunctive graph representation. In order to find scheduling policies that minimise the expectation of mean weighted tardiness, we propose a genetic programming based hyper heuristic to generate efficient dispatching rules. And then, based on the nested partition framework together with the optimal computing budget allocation technique, a hybrid rule selection algorithm is proposed for searching machine group specified rule combinations. Numerical results show that the proposed algorithms outperform benchmark algorithms in both solution quality and robustness.

Keywords:

References

Arroyo, JEC, JYT Leung and RG Tavares (2019). An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times. Engineering Applications of Artificial Intelligence, 77, 239–254. Web of Science, Google Scholar
Branke, J, S Nguyen, CW Pickardt and M Zhang (2015). Automated design of production scheduling heuristics: A review. IEEE Transactions on Evolutionary Computation, 20(1), 110–124. Web of Science, Google Scholar
Chen, C and LH Lee (2011). Stochastic Simulation Optimization: An Optimal Computing Budget Allocation. Singapore: World Scientific. Google Scholar
Chen, CH, J Lin, E Yücesan and SE Chick (2000). Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynamic Systems, 10(3), 251–270. Web of Science, Google Scholar
Chen, W, S Gao, CH Chen and L Shi (2014). An optimal sample allocation strategy for partition-based random search. IEEE Transactions on Automation Science and Engineering, 11(1), 177–186. Web of Science, Google Scholar
Fowler, J and J Robinson (1995). Measurement and improvement of manufacturing capacities (mimac): Final report. Technical Report 95062861A-TR, SEMATECH, Austin, TX. Google Scholar
Freitag, M and T Hildebrandt (2016). Automatic design of scheduling rules for complex manufacturing systems by multi-objective simulation-based optimization. CIRP Annals, 65(1), 433–436. Web of Science, Google Scholar
Gao, F, S Gao, H Xiao and Z Shi (2018). Advancing constrained ranking and selection with regression in partitioned domains. IEEE Transactions on Automation Science and Engineering, 16(1), 382–391. Web of Science, Google Scholar
Gao, F, Z Shi, S Gao and H Xiao (2019). Efficient simulation budget allocation for subset selection using regression metamodels. Automatica, 106, 192–200. Web of Science, Google Scholar
Geiger, CD, R Uzsoy and H Aytuğ (2006). Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling, 9(1), 7–34. Web of Science, Google Scholar
Gokhale, R and M Mathirajan (2011). Heuristic algorithms for scheduling of a batch processor in automobile gear manufacturing. International Journal of Production Research, 49(10), 2705–2728. Web of Science, Google Scholar
Gokhale, R and M Mathirajan (2014). Minimizing total weighted tardiness on heterogeneous batch processors with incompatible job families. The International Journal of Advanced Manufacturing Technology, 70(9–12), 1563–1578. Web of Science, Google Scholar
Hildebrandt, T, D Goswami and M Freitag (2014). Large-scale simulation-based optimization of semiconductor dispatching rules, in Proceedings of the 2014 Winter Simulation Conference, IEEE Press, pp. 2580–2590. Google Scholar
Ikura, Y and M Gimple (1986). Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 5(2), 61–65. Web of Science, Google Scholar
Jakobović, D and L Budin (2006). Dynamic scheduling with genetic programming, in European Conference on Genetic Programming, pp. 73–84, Springer. Google Scholar
Kanet, JJ and X Li (2004). A weighted modified due date rule for sequencing to minimize weighted tardiness. Journal of Scheduling, 7(4), 261–276. Web of Science, Google Scholar
Knopp, S, S Dauzère-Pérès and C Yugma (2017). A batch-oblivious approach for complex job-shop scheduling problems. European Journal of Operational Research, 263(1), 50–61. Web of Science, Google Scholar
Koza, JR and JR Koza (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press. Google Scholar
Lee, YH, K Bhaskaran and M Pinedo (1997). A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions, 29(1), 45–52. Web of Science, Google Scholar
Lenstra, JK, AR Kan and P Brucker (1977). Complexity of machine scheduling problems, in Annals of Discrete Mathematics, Elsevier, pp. 343–362. Google Scholar
Liu, P, X Zhang, Z Shi and Z Huang (2017). Simulation optimization for mro systems operations. Asia-Pacific Journal of Operational Research, 34(2), 1750003. Link, Web of Science, Google Scholar
Mason, S, J Fowler, W Carlyle and D Montgomery (2005). Heuristics for minimizing total weighted tardiness in complex job shops. International Journal of Production Research, 43(10), 1943–1963. Web of Science, Google Scholar
Mathirajan, M and A Sivakumar (2006). Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families. The International Journal of Advanced Manufacturing Technology, 28(9–10), 1038. Web of Science, Google Scholar
Neuts, MF (1967). A general class of bulk queues with poisson input. The Annals of Mathematical Statistics, 38(3), 759–770. Google Scholar
Nong, Q, C Ng and TE Cheng (2008). The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan. Operations Research Letters, 36(1), 61–66. Web of Science, Google Scholar
Ovacik, I and R Uzsoy (1997). Decomposition Methods for Complex Factory Scheduling Problems. Kluwer Academic Publishers. Google Scholar
Pickardt, C, J Branke, T Hildebrandt, J Heger and B Scholz-Reiter (2010). Generating dispatching rules for semiconductor manufacturing to minimize weighted tardiness, in Proceedings of the 2010 Winter Simulation Conference, IEEE, pp. 2504–2515. Google Scholar
Pickardt, CW, T Hildebrandt, J Branke, J Heger and B Scholz-Reiter (2013). Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems. International Journal of Production Economics, 145(1), 67–77. Web of Science, Google Scholar
Schapire, RE (1990). The strength of weak learnability. Machine Learning, 5(2), 197–227. Web of Science, Google Scholar
Shi, L and S Ólafsson (2000). Nested partitions method for global optimization. Operations Research, 48(3), 390–407. Web of Science, Google Scholar
Shi, Z, S Gao, J Du, H Ma and L Shi (2019). Automatic design of dispatching rules for real-time optimization of complex production systems. in 2019 IEEE/SICE International Symposium on System Integration (SII), IEEE, pp. 55–60. Google Scholar
Xu, J, E Huang, CH Chen and LH Lee (2015). Simulation optimization: A review and exploration in the new era of cloud computing and big data. Asia-Pacific Journal of Operational Research, 32(3), 1550019. Link, Web of Science, Google Scholar
Xu, J, S Zhang, E Huang, CH Chen, LH Lee and N Celik (2016). Mo2tos: Multi-fidelity optimization with ordinal transformation and optimal sampling. Asia-Pacific Journal of Operational Research, 33(3), 1650017. Link, Web of Science, Google Scholar