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

Hua-Ping Wu; Min Huang; W. H. Ip; Qun-Lin Fan

doi:10.3934/jimo.2016040

Article Contents

2017, Volume 13, Issue 2: 681-695. Doi: 10.3934/jimo.2016040

This issue Previous Article The bundle scheme for solving arbitrary eigenvalue optimizations Next Article Parallel-machine scheduling with potential disruption and positional-dependent processing times

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
* Corresponding author

Received: February 28, 2014

Revised: December 31, 2015

Published: August 2017

Abstract Full Text(HTML) Figure(10) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Table 1. Comparison of results among algorithms

$n$	$b$	$\lambda$	Average error rate		Average CPU time(s)
$n$	$b$	$\lambda$	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

| Show Table

DownLoad: CSV

Table 2. Comparison of results among algorithms

$n$	$b$	$\lambda$	AER		Time(s)
$n$	$b$	$\lambda$	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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.