**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(*n*^{2}) 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).

Transactions on Industrial Engineering (E)

January and February 2018Pages 370-385