Single-machine scheduling considering carryover sequence-dependent setup time, and earliness and tardiness penalties of production

Document Type: IIEC 2020


Department of Industrial Engineering, Faculty of Engineering, Shahed University, Tehran, Iran


Production scheduling is one of the very important problems that industry and production are confronted with it. Production scheduling is often planned in the industrial environments while productivity in production can improve significantly the expansion of simultaneous optimization of the scheduling plan. Production scheduling and production are two areas that have attracted much attention in the industry literature and production and research in the operation systems. In this study, the problem of single-machine scheduling with linear earliness and tardiness costs considering the work failure, energy consumption restriction, and the allowed idleness have been investigated and a new nonlinear mathematical model has been presented for the single-machine scheduling problem. Considering complexity in solution, this problem has been regarded as NP-hard problem. However, using methods that produce optimized results, it is just suitable for small size problems. Based on this, a genetic algorithm has been presented for solving this problem in average and large sizes. Numerical samples show that the presented algorithm is effective and efficient.


Main Subjects

Alemão, D., Parreira-Rocha, M., & Barata, J. (2018, January). Production and Maintenance Scheduling Supported by Genetic Algorithms. In International Precision Assembly Seminar (pp. 49-59). Springer, Cham.


Aouam, T., Geryl, K., Kumar, K., & Brahimi, N. (2018). Production planning with order acceptance and demand uncertainty. Computers & Operations Research91, 145-159.


Cochran, W. G., & Cox, G. M. (1992). Notes on the statistical analysis of the results.

da Rocha, J. S. A., Sala, A. D., de Almeida, E. B., Mancusi, F. C. M., Gerolin, F. S. F., Bucione, F. T. S., ... & Moraes, S. (2016). Relato de experiência: construção do modelo assistencial Hospital Alemão Oswaldo Cruz. Revista Acreditação: ACRED6(11), 72-85.


da Silva, N. C. O., Scarpin, C. T., Pécora Jr, J. E., & Ruiz, A. (2019). Online single machine scheduling with setup times depending on the jobs sequence. Computers & Industrial Engineering129, 251-258.


Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning.

Joo, C. M., & Kim, B. S. (2013). Genetic algorithms for single machine scheduling with time-dependent deterioration and rate-modifying activities. Expert Systems with Applications40(8), 3036-3043.. Expert Systems with Applications, 41 (2), 3136-3143.


Liu, Q., Dong, M., Chen, F. F., Lv, W., & Ye, C. (2019). Single-machine-based joint optimization of predictive maintenance planning and production scheduling. Robotics and Computer-Integrated Manufacturing55, 173-182.


Montgomery, D. T., & Reitz, R. D. (2000). Optimization of heavy-duty diesel engine operating parameters using a response surface method. SAE transactions, 1753-1765.


Niu, S., Song, S., Ding, J. Y., Zhang, Y., & Chiong, R. (2019). Distributionally robust single machine scheduling with the total tardiness criterion. Computers & Operations Research101, 13-28.


Pei, J., Cheng, B., Liu, X., Pardalos, P. M., & Kong, M. (2019). Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time. Annals of Operations Research272(1-2), 217-241.


Sabouni, M. Y., & Jolai, F. (2010). Optimal methods for batch processing problem with makespan and maximum lateness objectives. Applied Mathematical Modelling34(2), 314-324.


Sun, X., & Geng, X. N. (2019). Single-machine scheduling with deteriorating effects and machine maintenance. International Journal of Production Research57(10), 3186-3199.


Taguchi, G. (1986). Introduction to quality engineering: designing quality into products and processes (No. 658.562 T3).


Zhou, B., & Peng, T. (2019). New single machine scheduling with nonnegative inventory constraints and discretely controllable processing times. Optimization Letters13(5), 1111-1142.