Single machine scheduling to minimize the maximum tardiness under piecewise linear deteriorating jobs

Authors

Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran

Abstract

In many realistic production environments, jobs will take longer time if they begin later. This phenomenon is known as deteriorating jobs which have widely been studied. In this paper, the piecewise linear deterioration is discussed in a single machine scheduling problem of minimizing the maximum tardiness. After proving the NP-hardness of problem, a Branch and Bound and a heuristic algorithm with O(n2) are proposed for solving the large scale problems to near optimal solutions. The heuristic approach is also used to determine an upper bound on the solution of B&B algorithm. The computational results for evaluating performance of the two algorithms confirm the excellent performance of B&B algorithm as it is able to solve the problems with at least 32 jobs within a reasonable time. Notably, the heuristic approach is quite accurate and efficient with an average error percentage of less than 0.3%.

Keywords

Main Subjects


References

1. Jafari, A. and Moslehi, G. Scheduling linear deteriorating jobs to minimize the number of tardy jobs", Journal of Global Optimization, 54(2), pp. 389-404 (2012).

2. Lee, WC. and Lu, Z.S. Group scheduling with deteriorating jobs to minimize the total weighted number
of late jobs", Applied Mathematics and Computation,
218(17), pp. 8750-8757 (2012).
3. Moslehi, G. and Jafari, A. Minimizing the number
of tardy jobs under piecewise-linear deterioration",
Computers & Industrial Engineering, 59(4), pp. 573-
584 (2010).
4. Pinedo, M., Scheduling: Theory, Algorithms, and
Systems, 3th Ed., Upper Saddle River, Prentice Hall
(2002).
5. Yin, Y., Cheng, T.C.E. andWu, C.C. Scheduling with
time-dependent processing times 2015, Mathematical
Problems in Engineering, Article ID 367585, 2 pages
(2015).
6. Yin, Y., Cheng, T.C.E. and Wu, C.C. Scheduling
with time-dependent processing times", Mathematical
Problems in Engineering, Article ID 201421, 2 pages
(2014).
7. Alidaee, B. and Womer, N.K. Scheduling with time
dependent processing times: Review and extensions",
Journal of the Operational Research Society, 50(7), pp.
711-720 (1999).
8. Cheng, T.C.E., Ding, Q. and Lin, B.M.T. A concise
survey of scheduling with time-dependent processing
times", European Journal of Operational Research,
152(1), pp. 1-13 (2004).
9. Browne, S. and Yechiali, U. Scheduling deteriorating
jobs on a single processor", Computers & Operations
Research, 38(3), pp. 495-498 (1990).
10. Bachman, A. and Janiak, A. Minimizing maximum
lateness under linear deterioration theory and methodology",
European Journal of Operational Research,
126(3), pp. 557-566 (2000).
11. Hsu, Y.S. and Lin, B.M.T. Minimization of maximum
lateness under linear deterioration", Omega, 31(6), pp.
459-469 (2003).
12. Ng, C.T., Wang, J.B., Cheng, T.C.E. and Liu, L.L. A
branch-and-bound algorithm for solving a two-machine

ow shop problem with deteriorating jobs", Computers
& Operation Research, 37(1), pp. 83-90 (2010).
13. Lee, W.C., Yeh, W.C. and Chung, Y.H. Total tardiness
minimization in permutation
owshop with deterioration
consideration", Applied Mathematical Modelling,
38(13), pp. 3081-3092 (2014).
14. Yin, Y., Wang, Y., Cheng, T.C.E., Liu, W. and Li, J.
Parallel-machine scheduling of deteriorating jobs with
potential machine disruptions", Omega, 69, pp. 17-28
(2017).
15. Luo, W., and Ji, M. Scheduling a variable maintenance
and linear deteriorating jobs on a single machine",
Information Processing Letters, 115, pp. 33-39
(2015).
16. Lee, W.C., Wu, C.C. and Chung, Y.H. Scheduling
deteriorating jobs on a single machine with release
times", Computers & Industrial Engineering, 54(3),
pp. 441-452 (2008).
17. Wu, C.C. and Lee, W.C. Two-machine
owshop
scheduling to minimize mean
ow time under linear
deterioration", International Journal of Production
Economics, 103(2), pp. 572-584 (2006).
18. Lee, W.C., Wu, C.C., Wen, C.C. and Chung, Y.H.
A two-machine
owshop makespan scheduling problem
with deteriorating jobs", Computers & Industrial
Engineering, 54(4), pp. 737-749 (2008).
19. Wang, J.B. and Wang, M.Z. Minimizing makespan
in three-machine
ow shops with deteriorating jobs",
Computers & Operation Research, 40(2), pp. 547-557
(2013).
20. Yin, Y., Cheng, T.C.E., Wan, L., Wu, C.C. and Liu,
J. Two-agent single-machine scheduling with deteriorating
jobs", Computers & Industrial Engineering, 81,
pp. 177-185 (2015).
21. Mosheiov, G. Scheduling jobs under simple linear deA.
A. Jafari and M.M. Lot /Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 370{385 383
terioration", Computers & Operation Research, 21(6),
pp. 653-659 (1994).
22. Wang, J.B., Ng, C.T.D., Chen, T.C.E. and Liu,
L.L. Minimizing total completion time in a twomachine

ow shop with deteriorating jobs", Applied
Mathematics and Computation, 180(1), pp. 185-193
(2006).
23. Yang, S.H. andWang, J.B. Minimizing total weighted
completion time in a two-machine
ow shop scheduling
under simple linear deterioration", Applied Mathematics
and Computation, 217(9), pp. 4819-4826 (2011).
24. Wu, C.C. and Lee, W.C. Scheduling linear deteriorating
jobs to minimize makespan with an availability
constraint on a single machine", Information Processing
Letters, 87(2), pp. 89-93 (2003).
25. Cheng, T.C.E., Hsu, C.J., Huang, Y.C. and Lee, W.C.
Single-machine scheduling with deteriorating jobs
and setup times to minimize the maximum tardiness",
Computers & Operation Research, 38(12), pp. 1760-
1765 (2011).
26. Lee, W.C., Lin, J.B. and Shiau, Y.R. Deteriorating
job scheduling to minimize the number of late jobs with
setup times", Computers & Industrial Engineering,
61(3), pp. 782-787 (2011).
27. Kubiak, W. and Velde, S. Scheduling deteriorating
jobs to minimize makespan", Naval Research Logistics,
45(5), pp. 511-523 (1998).
28. Lalla Ruiz, E. and Vob, S. Modeling the parallel machine
scheduling problem with step deteriorating jobs",
European Journal of Operational Research, 255(1), pp.
21-33 (2016).
29. Jafari, A. and Moslehi, G. Minimizing the weighted
number of tardy jobs on a single machine under piecewise
linear deterioration", 9th International Industrial
Engineering Conference, Tehran, Iran (2013).
30. Lai, P., Wu, C. and Lee, W. Single machine scheduling
with logarithm deterioration", Optimization Letters,
6(8), pp. 1719-1730 (2011).
31. Lee, C. and Yu, G. Parallel machine scheduling under
potential disruption", Optimization Letters, 2(1), pp.
27-37 (2008).