Minimizing the sum of earliness and tardiness in single-machine scheduling

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

2 Assistant professor of department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

10.22070/jqepo.2021.14612.1191

Abstract

Today, the concept of JIT production has usage in production management and inventory control widely. In such an environment, tardiness or earliness is essential. Therefore, scheduling tries to minimize the sum of earliness and tardiness, which represents customer satisfaction, as well as inventory control. Most studies in scheduling adopt the assumption that machines are continuously available during the planning horizon. But in the real world, some machines may be temporarily unavailable for reasons such as breakdowns or preventive maintenance activities. So, considering the unavailability as a constraint is necessary for scheduling problems in the JIT production system. In this study, the unavailability constraint has been investigated with two flexible modes on a single machine. In each period, the duration of unavailability corresponding to the continuous working time of the machine changes in a discrete manner and can adopt two different values. Since the objective function is irregular, unforced idleness may be useful, increasing the complexity of the problem. First, a binary integer mathematical programming model is presented. Due to the NP-Hardness of the problem under consideration, a genetic algorithm is proposed to solve the problem in large dimensions. To examine the performance of the Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), several problem instances are generated and solved, and the obtained results are compared with those obtained from solving the mathematical model with the GAMS software. The computational results indicate the proposed algorithm has a good performance with an average deviation of 0.87% and a reasonable computational time.

Keywords

References

Ahmadizar, F. and Eteghadipour, J. Single-machine earliness–tardiness scheduling with two competing agents and idle time. Engineering Optimization, 2017. 49(3): p. 499-512.
Ahmadizar, F. and Farhadi, S. Single-machine batch delivery scheduling with job release dates, due windows and earliness, tardiness, holding and delivery costs. Computers & Operations Research, 2015. 53: p. 194-205.
Benmansour, R., et al., Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance. Computers & Operations Research, 2014. 47: p. 106-113.
Chen, L., Wang, J. and Yang, W. A single machine scheduling problem with machine availability constraints and preventive maintenance. International Journal of Production Research, 2021. 59(9): p. 2708-2721.
Du, J. and Leung, J.Y.-T. Minimizing total tardiness on one machine is NP-hard. Mathematics of operations research, 1990. 15(3): p. 483-495.
Feldmann, M. and Biskup, D. Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches. Computers & Industrial Engineering, 2003. 44(2): p. 307-323.
Ganji, F., Moslehi, G. and Ghalebsaz Jeddi, B. Minimizing maximum earliness in single-machine scheduling with flexible maintenance time. Scientia Iranica, 2017. 24(4): p. 2082-2094.
Jayanthi, S. and Anusuya, S. Minimization of total weighted earliness and tardiness using PSO for one machine scheduling. International Journal of Pure and Applied Mathematical Sciences, 2017. 10(1): p. 35-44.
Kellerer, H., Rustogi, K. and Strusevich, V.A. A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date. Omega, 2020. 90: p. 101992.
Khanh Van, B. and Van Hop, N. Genetic algorithm with initial sequence for parallel machines scheduling with sequence dependent setup times based on earliness-tardiness. Journal of Industrial and Production Engineering, 2021. 38(1): p. 18-28.
Lin, S.-W., et al., Single machine job sequencing with a restricted common due window. IEEE Access, 2019. 7: p. 148741-148755.
Low, C., Li, R.-K. and Wu, G.-H. Minimizing total earliness and tardiness for common due date single-machine scheduling with an unavailability interval. Mathematical Problems in Engineering, 2016. 6: p. 1-12.
Luo, W., Cheng, T.E. and Ji, M. Single-machine scheduling with a variable maintenance activity. Computers & Industrial Engineering, 2015. 79: p. 168-174.
Mahnam, M., Moslehi, G. and Ghomi, S.M.T.F. Single machine scheduling with unequal release times and idle insert for minimizing the sum of maximum earliness and tardiness. Mathematical and Computer Modelling, 2013. 57(9-10): p. 2549-2563.
Mashkani, O. and Moslehi, G. Minimising the total completion time in a single machine scheduling problem under bimodal flexible periodic availability constraints. International Journal of Computer Integrated Manufacturing, 2016. 29(3): p. 323-341.
M’Hallah, R. and Alhajraf, A. Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem. Journal of Scheduling, 2016. 19(2): p. 191-205.
Mozaffariyan, S. and Sahraeian, R. Single-machine scheduling considering carryover sequence-dependent setup time, and earliness and tardiness penalties of production. Journal of Industrial and Systems Engineering, 2020. 13(Special issue: 16th International Industrial Engineering Conference): p. 112-120.
Niroomand, S., et al., Hybrid greedy algorithms for fuzzy tardiness/earliness minimisation in a special single machine scheduling problem: case study and generalisation. International Journal of Computer Integrated Manufacturing, 2016. 29(8): p. 870-888.
Pacheco, J., et al., Variable neighborhood search with memory for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times. Knowledge-Based Systems, 2018. 145: p. 236-249.
Sadeghi, H., A forecasting system by considering product reliability, POQ policy, and periodic demand. Journal of Quality Engineering and Production Optimization, 2019. 4(2): p. 133-148.
Sajadi, S., Arianezhad, M.G. and Sadeghi, H.A. An Improved WAGNER-WHITIN Algorithm. 2009. 20(3): p. 117-123.
Sadeghi, H., Golpîra, H. and Khan, S.A.R. Optimal integrated production-inventory system considering shortages and discrete delivery orders. Computers & Industrial Engineering, 2021. 156: p. 107233.
Shahriari, M., et al., JIT single machine scheduling problem with periodic preventive maintenance. Journal of Industrial Engineering International, 2016. 12(3): p. 299-310.
Touat, M., et al., A hybridization of genetic algorithms and fuzzy logic for the single-machine scheduling with flexible maintenance problem under human resource constraints. Applied Soft Computing, 2017. 59: p. 556-573.
Tsai, T.-I., A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due dates and ready times. The International Journal of Advanced Manufacturing Technology, 2007. 31(9-10): p. 994-1000.
Wan, L. and Yuan, J. Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard. Operations Research Letters, 2013. 41(4): p. 363-365.
Wang, J.-B., Hu, Y. and Zhang, B. Common due-window assignment for single-machine scheduling with generalized earliness/tardiness penalties and a rate-modifying activity. Engineering Optimization, 2021. 53(3): p. 496-512.
Xiong, X., et al., Single-machine scheduling and common due date assignment with potential machine disruption. International Journal of Production Research, 2018. 56(3): p. 1345-1360.
Yuce, B., et al., Hybrid Genetic Bees Algorithm applied to single machine scheduling with earliness and tardiness penalties. Computers & Industrial Engineering, 2017. 113: p. 842-858.
Journal of Quality Engineering and Production Optimization
Volume 6, Issue 2
December 2021
Pages 59-78

Files

Share

How to cite

Statistics