# American Institute of Mathematical Sciences

April  2017, 13(2): 681-695. doi: 10.3934/jimo.2016040

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

 1 Accounting R & D Center, Chongqing University of Technology, Chongqing 400054, China 2 College of Information Science and Engineering, Northeastern University, State Key Laboratory of Integrated Automation of Process Industry (Northeastern University) Shenyang 110004, China 3 Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hong Kong 110004, China 4 College of Management, Chongqing University of Technology, Chongqing 400054, China

* Corresponding author

Received  March 2014 Revised  January 2016 Published  May 2016

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.

Citation: Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040
##### References:

show all references

##### References:
The generic partitions for the single machine scheduling problem
The effect of $\lambda$ on average error rate based on $b=0.05$
The effect of $\lambda$ on average CPU time based on $b=0.05$
The effect of $\lambda$ on average error rate based on $b=0.1$
The effect of $\lambda$ on average CPU time based on $b=0.1$
The effect of $b$ on average error rate based on $\lambda=0.2$
The effect of $b$ on average CPU time based on $\lambda=0.2$
The effect of $b$ on average error rate based on $\lambda=3.0$
The effect of $b$ on average CPU time based on $\lambda=3.0$
The CPU time of several algorithms with respect to n
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
 $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
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
 $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] Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825 [2] Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323 [3] Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088 [4] Thomas Ward, Yuki Yayama. Markov partitions reflecting the geometry of $\times2$, $\times3$. Discrete & Continuous Dynamical Systems - A, 2009, 24 (2) : 613-624. doi: 10.3934/dcds.2009.24.613 [5] Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 [6] P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95 [7] Zhao-Hong Jia, Ting-Ting Wen, Joseph Y.-T. Leung, Kai Li. Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 977-993. doi: 10.3934/jimo.2016057 [8] Zhimin Zhang. On a risk model with randomized dividend-decision times. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1041-1058. doi: 10.3934/jimo.2014.10.1041 [9] Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041 [10] Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 [11] Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71 [12] Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691 [13] Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial & Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076 [14] Maria Antonietta Farina, Monica Marras, Giuseppe Viglialoro. On explicit lower bounds and blow-up times in a model of chemotaxis. Conference Publications, 2015, 2015 (special) : 409-417. doi: 10.3934/proc.2015.0409 [15] Giuseppe D'Onofrio, Enrica Pirozzi. Successive spike times predicted by a stochastic neuronal model with a variable input signal. Mathematical Biosciences & Engineering, 2016, 13 (3) : 495-507. doi: 10.3934/mbe.2016003 [16] Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849 [17] Michael Hochman. Smooth symmetries of $\times a$-invariant sets. Journal of Modern Dynamics, 2018, 13: 187-197. doi: 10.3934/jmd.2018017 [18] Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647 [19] Aniello Buonocore, Luigia Caputo, Enrica Pirozzi, Maria Francesca Carfora. A simple algorithm to generate firing times for leaky integrate-and-fire neuronal model. Mathematical Biosciences & Engineering, 2014, 11 (1) : 1-10. doi: 10.3934/mbe.2014.11.1 [20] Madhu Jain, Sudeep Singh Sanga. Admission control for finite capacity queueing model with general retrial times and state-dependent rates. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-25. doi: 10.3934/jimo.2019073

2018 Impact Factor: 1.025

## Tools

Article outline

Figures and Tables