DNN Based Scheduler Towards Minimizing Setups and Tardiness in Unrelated Dedicated Parallel Machine with Job Splitting
Abstract
This paper addresses an unrelated dedicated parallel machine scheduling problem towards minimizing both setups and tardiness of allocated jobs. The scheduling problem considered in this study is the NP-hard problem well-known, and it contains many practical constraints such as setup, machine availability, preventive maintenance, and job splitting. To solve this problem, we propose a scheduler based on deep learning. The proposed scheduler is designed to learn the dependency between jobs consecutively assigned to a machine in terms of setup, tardiness, and the ratio of job splitting. As the experiment results, the scheduling performances of the proposed scheduler outperforms compared to the conventional rules-based schedulers. In particular, the proposed scheduler is superior to other schedulers for given the scheduling problems that easily occur more tardiness.
Full Text:
PDFReferences
Alvarez, J. M. and Salzmann, M., “Learning the number of neurons in deep networks,” Advances in Neural Information Processing Systems, Vol. 29, pp. 2270-2278, 2016.
Arık, O. A., Schutten, M., and Topan, E., “Weighted earliness/tardiness parallel machine scheduling problem with a common due date,” Expert Systems with Applications, Vol. 187, 2022.
Chen, J-F. and Wu, T-H., “Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints,” Omega, Vol. 34, No. 1, pp. 81-89, 2006.
Cobbe, K., Klimov, O., Hesse, C., Kim, T., and Schulman, J., “Quantifying generalization in reinforcement learning,” Proc. 36th Int. Conf. on Machine Learning, Vol. 97, pp. 1282-1289, 2019.
Ghosh, A., Kumar, H., and Sastry, P. S., “Robust loss functions under label noise for deep neural networks,” Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 31, No. 1, 2017.
Greff, K., Srivastava, R. K., Koutník, J., Steunebrink, B. R., and Schmidhuber, J., “LSTM: A search space odyssey,” IEEE Transactions on Neural Networks and Learning Systems, Vol. 28, No. 10, pp. 2222-2232, 2017.
Hamad, A., Sanugi, B., and Salleh, S., “A neural network model for the common due date job scheduling on unrelated parallel machines,” International Journal of Computer Mathematics, Vol. 80, pp. 845-851, 2003.
Kim, D-W., Na, D-G., and Chen, F. F., “Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective,” Robotics and Computer-Integrated Manufacturing, Vol. 19, pp. 173-181, 2003.
Kim, H.-J. and Lee, J.-H., “Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers,” Computers & Operations Research, Vol. 126, 2021.
Kim, J-G., Song, S., and Jeong, B., “Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times,” International Journal of Production Research, Vol. 58, No. 6, pp. 1628-1643, 2020.
Koh, S., Seo, W., and Kim, S., “Two-stage non-identical parallel machine scheduling with genetic algorithm,” Journal of the Korean Institute of Industrial Engineers, Vol. 47, No. 1, pp. 1-10, 2021.
Lamothe, J., Marmier, F., Dupuy, M., Gaborit, P., and Dupont, L., “Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints,” Computers and Operations Research, Vol. 39, No. 6, pp. 1236-1244, 2012.
Lee, J-H., Kim, S. H., and Lee, Y. H., “Discrete lot sizing and scheduling problem under batch processing constraints in the semiconductor manufacturing,” The International Journal of Advanced Manufacturing Technology, Vol. 69, pp. 383-396, 2013.
Lee, J-H., Yu, J-M., and Lee, D-H., “A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness,” The International Journal of Advanced Manufacturing Technology, Vol. 69, pp. 2081-2089, 2013.
Lee, Y. H., Bhaskaran, K., and Pinedo, M., “A heuristic to minimize the total weighted tardiness with sequence- dependent setups,” IIE Transactions, Vol. 29, pp. 45-52, 1997.
Li, Z., Yang, H., Zhang, S., and Liu, G., “Unrelated parallel machine scheduling problem with energy and tardiness cost,” The International Journal of Advanced Manufacturing Technology, Vol. 84, pp. 213-226, 2016.
Liaw, C-F., Lin, Y-K., Cheng, C-Y., and Chen, M., “Scheduling Unrelated Parallel Machines to Minimize Total Weighted Tardiness,” Computers & Operations Research, Vol. 30, No. 12, pp. 1777-1789, 2003.
Lin, S-W. and Ying, K-C., “A Multi-Point Simulated Annealing Heuristic for Solving Multiple Objective Unrelated Parallel Machine Scheduling Problems,” International Journal of Production Research, Vol. 53, pp. 1065-1076, 2014.
Lin, S.-W., Ying, K.-C., Wu, W.-J., and Chiang, Y.-I., “Multi-objective unrelated parallel machine scheduling: A tabu-enhanced iterated pareto greedy algorithm,” International Journal of Production Research, Vol. 54, No. 4, pp. 1110-1121, 2016.
Nair, V. and Hinton, G. E., “Rectified linear units improve restricted boltzmann machines,” ICML 2010, pp. 807-814, 2010.
Paeng, B., Park, I-B., and Park, J., “Deep reinforcement learning for minimizing tardiness in parallel machine scheduling with sequence dependent family setups,” IEEE Access, Vol. 9, 2021.
Pickardt, C., Branke, J., Hildebrandt, T., Heger, J., and Scholz-Reiter, B., “Generating dispatching rules for semiconductor manufacturing to minimize weighted tardiness,” Proc. of the 2010 Winter Simulation Conf., pp. 2504-2515, 2010.
Pinedo, M., Scheduling : Theory, Algorithms, and Systems, Prentice Hall, New Jersey, U.S.A., 2002.
Ren, H., Jiang, L., Xi, X., and Li, M., “Heuristic optimization for dual-resource constrained job shop scheduling,” 2009 Int. Asia Conf. on Informatics in Control, Automation and Robotics, pp. 485-488, 2009.
Ribas, I., Leisten, R., and Framiñan, J. M., “Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective,” Computers and Operations Research, Vol. 37, pp. 1439-1454, 2010.
Salimifard, K., Li, J., and Mohammadi, D., “A multi objective volleyball premier league algorithm for green scheduling identical parallel machines with splitting jobs,” Applied Intelligence, Vol. 51, No. 7, pp. 4143-4161, 2021.
Schaller, J. E., Gupta, J. N. D., and Vakharia, A. J., “Scheduling a flowline manufacturing cell with sequence dependent family setup times,” European Journal of Operational Research, Vol. 125, No. 2, pp. 324-339, 2000.
Souk, J., Morozumi, S., Luo, F-C., and Bita, I., Flat Panel Display Manufacturing, John Wiley & Sons, New Jersey, U.S.A., 2018.
Uto, M. and Okano, M., “Robust neural automated essay scoring using item response theory,” Artificial Intelligence in Education, pp. 549-561, 2020.
Vesterlund, M., Toffolo, A., and Dahl, J., “Optimization of multi-source complex district heating network, a case study,” Energy, Vol. 126, pp. 53-63, 2017.
Wang, X., Li, Z., Chen, Q., and Mao, N., “Meta-heuristics for unrelated parallel machines scheduling with random rework to minimize expected total weighted tardiness,” Computers & Industrial Engineering, Vol. 145, 2020.
Wei, Q., Fei, N., Islam, A., Lei, T., Hong, L., Peng, R., Fan, X., Chen, Gao, P., and Ge, Z., “Small-molecule emitters with high quantum efficiency: Mechanisms, structures, and applications in OLED devices,” Advanced Optical Materials, Vol. 6, No. 20, 2018.
Xue, G., Felix, O. O., Zhou, H., and Troutt, MD., “Integrated production planning with sequence-dependent family setup times,” International Journal of Production Economics, Vol. 131, pp. 674-681, 2011.
Yang-Kuei, L. and Chi-Wei, L., “Dispatching rules for unrelated parallel machine scheduling with release dates,” The International Journal of Advanced Manufacturing Technology, Vol. 67, pp. 269-279, 2013.
Yao, X., Fernandez-Gaucherand, E., Fu, M. C., and Marcus, S. I., “Optimal preventive maintenance scheduling in semiconductor manufacturing,” IEEE Transactions on Semiconductor Manufacturing, Vol. 17, No. 3, 2004.
Yoo, W., Seo, J., Lee, D., Kim, D., and Kim, K., “Scheduling generation model on parallel machines with due date and setup cost based on deep learning,” The Journal of Society for e-Business Studies, Vol. 24, No. 3, pp. 99-110, 2019.
Zhang, Z., Zheng, L., Li, N., Wang, W., Zhong, S., and Hu, K., “Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning,” Computers & Operations Research, Vol. 39, No. 7, pp. 1315-1324, 2012.
Refbacks
- There are currently no refbacks.