Minimizing makespan in a single machine scheduling problem with deteriorating jobs and learning effects

ABSTRACT

This paper considers a single machine scheduling problem with simultaneous deteriorating jobs and learning effects. It is proved in the literature that the single machine scheduling problem with linear deterioration rate and learning effect is NP-hard in strong sense. Therefore, due to complexity of the problem finding the best sequence of jobs with minimum Makespan using Full Enumeration methods is time consuming and costly. Therefore, a new polynomial time heuristic algorithm is proposed to solve the problem in different sizes. The performance of the heuristic algorithm is evaluated against classical Smallest Deterioration Rate and Full Enumeration methods in solving various test problems. For this purpose, different measures including Percentage Relative Error and CPU_Time are considered to demonstrate the superior solution method. In addition, Single Factor ANOVA and Tukey's multiple comparison test are utilized to find significant differences in performance of the solution methods.

References

1. W.C. Lee, C.C. Wu, "Multi-machine scheduling with deteriorating jobs and scheduled maintenance", Appl. Math. Model., vol. 32, Mar. 2008, pp. 362--373
2. E. G. Coffman, Jr, M. R. Garey, D. S. Johnson, "An application of bin-packing to multiprocessor scheduling". SIAM J. on Comput, vol. 7, Feb. 1978, pp. 1--17
3. W.C. Lee, C.C. Wu, "A note on single-machine group scheduling problems with position-based learning effect", Appl. Math. Model., vol. 33, Apr. 2009, pp. 2159--2163
4. T.C.E. Cheng, C.C. Wu, W.C. Lee, "Some scheduling problems with deteriorating jobs and learning effects", Comput. and Indust. Eng, vol. 54, May. 2008, pp. 972--982
5. P. Liu, L. Tang, X. Zhou, "Two-agent group scheduling with deteriorating jobs on a single machine", Int. J. of Adv. Manuf. Tech, vol. 47, Mar. 2010, pp. 657--664
6. J.B. Wang, "Single machine scheduling with a time-dependent learning effect and deteriorating jobs", J. of the Operat. Res. Soc, vol. 60, Apr. 2009, pp. 583--586
7. J.B. Wang, Y. Jiang, G. Wang, 2009. "Single machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning", Int. J. of Adv. Manuf. Tech, vol. 41, Apr. 2009, pp. 1221--1226
8. J.B. Wang, Q. Guo, 2010. "A due-date assignment problem with learning effect and deteriorating jobs", Appl. Math. Model., vol. 34, Feb. 2010, pp. 309--313
9. X. Huang, M.Z. Wang, J.B. Wang, "Single-machine group scheduling with both learning effects and deteriorating jobs". Comput. and Indust. Eng, vol. 60, May. 2011, pp. 750--754
10. J.B Wang, D. Wang, G.D. Zhang,. "Single-machine scheduling problems with both deteriorating jobs and learning effects", Appl. Math. Model., vol. 34, Oct. 2010, pp 2831--2839
11. J. J. Kanet, "Minimizing variation of flow time in single machine systems". Manag. Sci, vol. 27, Dec. 1981, pp. 1453--1459
12. J.B. Wang, M.Z. Wang,. "Single-machine scheduling with nonlinear deterioration", Opt. Lett. vol. 6, Jan. 2012, pp. 87--98, doi: 0.1007/s11590-010-0253-3.
13. Y. Yin, T.C.E. Cheng, L. Wan, C.C. Wu, J. Liu, "Two-agent single-machine scheduling with deteriorating jobs". Comput. and Indust. Eng, vol. 81, Mar. 2015, pp. 177--185
14. P. Guo, W. Chen, Y. Wang, "A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs", arXiv preprint arXiv:1301.7134.
15. C. Zhao, H. Tang, "Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs". Comput. and Indust. Eng, vol. 59, Nov. 2010, pp. 663--666
16. S. H. Pakzad-Moghaddam, H. Mina, R. Tavakkoli-Moghaddam, "An approach for modeling a new single machine scheduling problem with deteriorating and learning effects". Comput. and Indust. Eng, vol. 78, Dec. 2014, pp. 33--43
17. W.C. Lee, "A note on deteriorating jobs and learning in single-machine scheduling problems". Int. J. of Bus. and Econ, vol. 3, Jan. 2004, pp. 83--89.
18. M. Ji, C.J. Hsu, D. L. Yang, "Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration". J. of Comb. Optim, (3), vol. 26, Oct. 2013, pp. 437--447
19. A. Bachman, A. Janiak, "Minimizing maximum lateness under linear deterioration". Euro. J. of Oper. Res, (3), vol. 126, Nov. 2000, pp. 557--566
20. D. Wang, J.B. Wang, "Single-machine scheduling with simple linear deterioration to minimize earliness penalties". The Int. J. of Adv. Manuf. Tech,, (1--4), vol. 46, Jan. 2010, pp. 285--290
21. S. Khalilpourazari, S.H.R. Pasandideh, "Multi-item EOQ model with nonlinear unit holding cost and partial backordering: moth-flame optimization algorithm". J of Indust. and Prod. Eng, Jun 2016, pp. 1--10
22. S. Khalilpourazari, S.H.R. Pasandideh, S.T.A. Niaki, "Optimization of multi-product economic production quantity model with partial backordering and physical constraints: SQP, SFS, SA, and WCA". Appl. Soft. Comput. Sep 2016
23. S. Khalilpourazari, M. Mohammadi, "Optimization of closed-loop Supply chain network design: a Water Cycle Algorithm approach". 12th Int. Conf. on Indust. Eng. IEEE. Jan. 2016, pp. 41--45
24. S. Khalilpourazari, S.H.R. Pasandideh, "Bi-objective optimization of multi-product EPQ model with backorders, rework process and random defective rate". 12th Int. Conf. on Indust. Eng. IEEE. Jan. 2016b, pp. 36--40
25. S. Khalilpourazari, S. Khalilpourazary, "A lexicographic weighted Tchebycheff approach for multi-constrained multi-objective optimization of the surface grinding process". Eng. Optimiz. Aug 2016, pp. 1--18
26. S. Khalilpourazari, S. Khalilpourazary, "Optimization of production time in the multi-pass milling process via a Robust Grey Wolf Optimizer". Neural Comput & Applic. 2016

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

    • Mathematical optimization