Article Contents
Article Contents

# Algorithms for single-machine scheduling problem with deterioration depending on a novel model

• * Corresponding author
• In this paper, a novel single machine scheduling problem with deterioration depending on waiting times is investigated. Firstly, a new deterioration model for the problem is presented. Secondly, according to characteristics of the problem, dominance properties and lower bounds are proposed and integrated into the Branch and Bound algorithm (B & B) to solve the small-medium scale problems. Thirdly, for solving a large-scale problem, the Rules Guided Nested Partitions method (RGNP) is proposed. The numerical experiments show that when the size of the problem is no more than 17 jobs, the B & B algorithm can obtain the optimal solutions in a reasonable time. The RGNP method can also obtain an average error percentage for near-optimal solutions less than 0.048 within 0.2s. The analysis shows the efficiency of RGNP, and, hence, it can be used for solving large size problems.

Mathematics Subject Classification: Primary: 90B50, 90B36; Secondary: 62P30.

 Citation:

• Figure 1.  The generic partitions for the single machine scheduling problem

Figure 2.  The effect of $\lambda$ on average error rate based on $b=0.05$

Figure 3.  The effect of $\lambda$ on average CPU time based on $b=0.05$

Figure 4.  The effect of $\lambda$ on average error rate based on $b=0.1$

Figure 5.  The effect of $\lambda$ on average CPU time based on $b=0.1$

Figure 6.  The effect of $b$ on average error rate based on $\lambda=0.2$

Figure 7.  The effect of $b$ on average CPU time based on $\lambda=0.2$

Figure 8.  The effect of $b$ on average error rate based on $\lambda=3.0$

Figure 9.  The effect of $b$ on average CPU time based on $\lambda=3.0$

Figure 10.  The CPU time of several algorithms with respect to n

Table 1.  Comparison of results among algorithms

 $n$ $b$ $\lambda$ Average error rate Average CPU time(s) RGNP ONP B & B RGNP ONP 5 0.05 0.2 0.000 0.000 1.07 0.00 0.00 1.0 0.034 0.054 1.26 0.00 0.00 3.0 0.000 0.000 0.94 0.00 0.00 0.10 0.2 0.000 0.004 1.17 0.00 0.00 1.0 0.000 0.000 1.36 0.00 0.00 3.0 0.000 0.005 0.82 0.00 0.00 Average CPU time 1.10 0.00 0.00 9 0.05 0.2 0.000 0.002 1.50 0.01 0.00 1.0 0.010 0.106 1.21 0.01 0.01 3.0 0.000 0.012 114.30 0.01 0.00 0.10 0.2 0.000 0.015 1.38 0.01 0.00 1.0 0.000 0.070 11.04 0.01 0.00 3.0 0.016 0.071 21.53 0.01 0.01 Average CPU time 1315.55 0.04 0.02 13 0.05 0.2 0.008 0.028 16.88 0.04 0.02 1.0 0.016 0.300 51.19 0.05 0.02 3.0 0.000 0.031 6041.71 0.06 0.01 0.10 0.2 0.028 0.057 13.16 0.04 0.02 1.0 0.021 0.221 35.32 0.05 0.02 3.0 0.000 0.109 1735.06 0.04 0.01 Average CPU time 25.16 0.01 0.00 17 0.05 0.2 0.018 0.038 1007.11 0.18 0.07 1.0 0.015 0.200 1222.28 0.18 0.07 3.0 0.012 0.216 38012.51 0.18 0.07 0.10 0.2 0.048 0.116 610.34 0.12 0.07 1.0 0.022 0.444 1958.67 0.12 0.07 3.0 0.012 0.245 18292.45 0.12 0.07 Average CPU time 10183.89 0.15 0.07

Table 2.  Comparison of results among algorithms

 $n$ $b$ $\lambda$ AER Time(s) RGNP ONP RGNP ONP 20 0.05 0.2 0.000 0.015 0.06 0.03 1.0 0.000 0.723 0.06 0.05 3.0 0.000 0.009 0.07 0.05 0.1 0.2 0.000 0.014 0.08 0.04 1.0 0.000 1.447 0.09 0.04 3.0 0.000 0.123 0.08 0.04 40 0.05 0.2 0.000 0.079 0.67 0.34 1.0 0.000 1.008 0.62 0.28 3.0 0.000 0.219 0.68 0.31 0.1 0.2 0.000 0.282 0.67 0.32 1.0 0.000 1.281 0.67 0.30 3.0 0.000 1.878 0.67 0.32 60 0.05 0.2 0.000 0.212 2.49 1.06 1.0 0.000 1.164 1.87 0.75 3.0 0.000 0.188 1.87 0.76 0.1 0.2 0.000 0.007 1.80 0.76 1.0 0.000 3.898 1.89 0.75 3.0 0.000 7.127 1.88 0.76 80 0.05 0.2 0.000 0.135 4.95 1.87 1.0 0.000 1.623 5.07 1.85 3.0 0.000 1.861 5.18 1.88 0.1 0.2 0.000 0.199 4.87 1.91 1.0 0.000 10.61 5.01 1.87 3.0 0.000 0.459 5.16 1.89 100 0.05 0.2 0.000 0.072 10.91 4.02 1.0 0.000 9.025 11.41 3.98 3.0 0.000 7.454 11.43 3.96 0.1 0.2 0.000 0.262 11.40 4.23 1.0 0.000 3.742 11.66 4.11 3.0 0.000 21.139 11.59 4.19 120 0.05 0.2 0.000 0.171 20.98 7.49 1.0 0.000 3.260 21.29 7.39 3.0 0.000 20.191 21.24 7.51 0.1 0.2 0.000 0.063 20.13 7.20 1.0 0.000 7.355 21.05 7.76 3.0 0.000 76.76 21.06 7.52
•  [1] S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498.  doi: 10.1287/opre.38.3.495. [2] T. C. E. Cheng and Q. Ding, The complexity of scheduling starting time dependent tasks with release times, Information Processing Letters, 65 (1998), 75-79.  doi: 10.1016/S0020-0190(97)00195-6. [3] T. C. E. Cheng, W. C. Lee and C. C. Wu, Single-machine scheduling with deteriorating functions for job processing times, Applied Mathematical Modelling, 34 (2010), 4171-4178.  doi: 10.1016/j.apm.2010.04.014. [4] C. B. Chu, A branch-and-bound algorithm to minimize total flow time with unequal release dates, Naval Research Logistics, 39 (1992), 859-875.  doi: 10.1002/1520-6750(199210)39:6<859::AID-NAV3220390610>3.0.CO;2-W. [5] R. J. Dakin, A tree-search algorithm for mixed integer programming problem, The Computer Journal, 8 (1965), 250-255.  doi: 10.1093/comjnl/8.3.250. [6] R. L. Graham, E. L. Lawler and J. K. Lenstra, Optimization and approximation in the deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X. [7] J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14 (1998), 387-393.  doi: 10.1016/0360-8352(88)90041-1. [8] I. Kacem and E. Levner, An Improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs, Journal of Industrial and Management Optimization, 12 (2016), 811-817. [9] P. J. Lai and W. C. Lee, Single-machine scheduling with a nonlinear deterioration function, Information Processing Letters, 110 (2010), 455-459.  doi: 10.1016/j.ipl.2010.04.012. [10] A. H. Land and A. G. Doig, An automatic method of solving discrete programming problems, Econometrica, 28 (1960), 497-520.  doi: 10.2307/1910129. [11] Y. K. Lin and C. S. Chong, A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 703-717.  doi: 10.3934/jimo.2016.12.703. [12] S. Olafsson and J. Yang, Intelligent partitioning for feature selection, INFORMS Journal on Computing, 17 (2005), 339-355.  doi: 10.1287/ijoc.1040.0104. [13] D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, Journal of the Operational Research Society, 1 (2014), 49-56. [14] L. Pi, Y. Pan and L. Shi, Hybrid nested partitions and mathematical programming approach and its applications, IEEE Transactions on Automation Science & Engineering, 5 (2008), 573-586. [15] J. Qian and G. Steiner, Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine, European Journal of Operational Research, 225 (2013), 547-551.  doi: 10.1016/j.ejor.2012.09.013. [16] A. J. Ruiz-Torres, G. Paletta and E. Pérez, Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects, Computers & Operations Research, 40 (2013), 2051-2061.  doi: 10.1016/j.cor.2013.02.018. [17] P. Shen, C. M. Wei and X. Huang, Single-machine scheduling problems with an actual time-dependent deterioration, Applied Mathematical Modelling, 37 (2013), 5555-5562.  doi: 10.1016/j.apm.2012.10.012. [18] L. Shi and S. Olafsson, Nested partitions method for global optimization, Operations Research, 48 (2000), 390-407.  doi: 10.1287/opre.48.3.390.12436. [19] L. Shi, S. Olafsson and Q. Chen, An optimization framework for product design, Management Science, 47 (2001), 1681-1692.  doi: 10.1287/mnsc.47.12.1681.10243. [20] S. A. Shihabi and S. Olafsson, A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem, Computers & Operations Research, 37 (2010), 247-255.  doi: 10.1016/j.cor.2009.04.015. [21] P. Yan, A. Che, X. Cai and X. Tang, Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance, Name of the Journal, 50 (2014), 128-140.  doi: 10.1016/j.cor.2014.04.002. [22] P. Yan, C. Chu, N. Yang and A. Che, A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows, International Journal of Production Research, 48 (2010), 6461-6480.  doi: 10.1080/00207540903225205. [23] Y. Yin, W. H. Wu, T. C. E. Cheng and C. C. Wu, Single-machine scheduling with time-dependent and position-dependent deteriorating jobs, International Journal of Computer Integrated Manufacturing, 28 (2015), 781-790.  doi: 10.1080/0951192X.2014.900872. [24] X. Zhang, D. Xu, D. Du and C. Miao, Approximate algorithms for unrelated machine scheduling to minimize makespan, Jorunal of Industrial and Management Optimization, 12 (2016), 771-779.  doi: 10.3934/jimo.2016.12.771.

Figures(10)

Tables(2)