Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects

Ping Yan; Ji-Bo Wang; Li-Qiang Zhao

doi:10.3934/jimo.2018088

Article Contents

2019, Volume 15, Issue 3: 1117-1131. Doi: 10.3934/jimo.2018088

This issue Previous Article Unified optimality conditions for set-valued optimizations Next Article Optimality conditions and duality for minimax fractional programming problems with data uncertainty

Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects

1.
School of Economics and Management, Shenyang Aerospace University, Shenyang 110136, China
2.
School of Science, Shenyang Aerospace University, Shenyang 110136, China

* Corresponding author
* Corresponding author

Received: September 30, 2016

Revised: February 28, 2018

Early access: June 2018

Published: April 2019

This research is partly supported by National Natural Science Foundation (Grant No. U1433124), the Humanities and Social Science Fund of the Ministry of Education (Grant No. 17YJA630139), Doctor Foundation of Liaoning Province (Grant No. 20170520175) and Social Science Planning Fund of Liaoning Province (Grant No. L16DGL007). Ji-Bo Wang was partially supported by the National Natural Science Foundation of China (Grant No. 71471120), the Support Program for Innovative Talents in Liaoning University (grant no. LR2016017) and the Liaoning BaiQianWan Talents Program.

Abstract Full Text(HTML) Figure(0) / Table(4) Related Papers Cited by

Abstract

This paper deals with a single machine bi-criterion scheduling problem with exponentially time-dependent learning effects and non-zero job release times. The goal is to minimize the weighted sum of the makespan and the total completion time. First, a branch-and-bound algorithm incorporating with some dominance properties and three lower bounds is developed for the optimal solutions. Then heuristic and particle swarm optimization algorithms are presented for near-optimal solutions. Finally, computational experiments are conducted to evaluate the performances of the proposed algorithms. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.

Keywords:

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.

Citation:

Full Text(HTML)

Table 1. Conversion process from a job permutation to a position vector of a particle

Dimension	1	2	3	4	5
Job permutation	4	1	3	5	2
${s_{HA, j}}$	2	5	3	1	4
${x_{HA, j}}$	2.09	-3.88	0.33	3.15	-2.11

| Show Table

DownLoad: CSV

Table 2. The performance of the branch-and-bound algorithm

$n$	$\alpha$	Node		cpu time
$n$	$\alpha$	Mean	Max	Mean	Max
20	0.6	156866	373724	3.462	8.001
	0.7	143956	399559	3.403	8.112
	0.8	119154	438721	2.963	8.898
	0.9	231118	708148	5.446	14.991
25	0.6	16365534	120686189	476.151	3476.91
	0.7	6657363	24736334	226.272	682.129
	0.8	2057701	7619907	69.852	228.938
	0.9	1654445	5476902	61.673	197.13
30	0.6	57205995.4	271309428	2034.489	9230.5
	0.7	163983353	793164929	3551.163	16301.3
	0.8	166549081.2	792800370	3535.774	14842.375
	0.9	183125835.4	781099881	4101.858	13852.2

| Show Table

DownLoad: CSV

Table 3. The performance of the heuristic and PSO algorithms with $n$ = 20, 25, 30

$n$	$\alpha$	Error percentage												cpu time
		$H{A_1}$		$H{A_2}$		$H{A_3}$		$PS{O_1}$		$PS{O_2}$		$PS{O_3}$		$PS{O_1}$		$PS{O_2}$		$PS{O_3}$
		Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max
20	0.6	44.876	81.861	0.019	0.192	3.404	5.749	0	0	0	0	0	0	0.218	0.234	0.212	0.234	0.217	0.219
	0.7	61.42	100.792	0.016	0.163	4.101	9.411	0	0	0	0	0	0	0.218	0.234	0.215	0.234	0.217	0.234
	0.8	59.038	104.588	0.066	0.618	3.054	5.542	0	0	0	0	0	0	0.219	0.234	0.214	0.234	0.217	0.219
	0.9	56.364	87.247	0.03	0.242	3.316	7.171	0	0	0	0	0	0	0.226	0.234	0.225	0.249	0.223	0.234
25	0.6	58.287	78.022	0	0	2.622	4.439	0	0	0	0	0	0	0.3	0.312	0.295	0.312	0.296	0.312
	0.7	50.031	64.443	0	0	3.474	5.486	0	0	0	0	0	0	0.304	0.327	0.298	0.312	0.301	0.327
	0.8	53.712	108.917	0.01	0.08	3.184	4.685	0	0	0	0	0	0	0.301	0.312	0.296	0.312	0.296	0.312
	0.9	55.843	69.099	0.051	0.364	3.007	5.37	0	0	0	0	0	0	0.3056	0.312	0.303	0.312	0.306	0.328
30	0.6	61.811	92.105	0	0	2.77	3.85	0	0	0	0	0	0	0.43	0.483	0.418	0.468	0.424	0.468
	0.7	67.222	85.626	0	0	2.827	3.469	0	0	0	0	0	0	0.399	0.406	0.39	0.405	0.393	0.406
	0.8	69.096	88.61	0	0	2.552	5.058	0	0	0	0	0	0	0.393	0.406	0.387	0.405	0.377	0.405
	0.9	64.549	85.241	0.01	0.026	2.787	3.487	0	0	0	0	0	0	0.412	0.421	0.399	0.406	0.399	0.406

| Show Table

DownLoad: CSV

Table 4. The performance of the heuristic and PSO algorithms for large-size jobs

$n$	$\alpha$	Relative deviance percentage												cpu time
		$H{A_1}$		$H{A_2}$		$H{A_3}$		$PS{O_1}$		$PS{O_2}$		$PS{O_3}$		$PS{O_1}$		$PS{O_2}$		$PS{O_3}$
		Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max
100	0.6	80.067	102.419	0	0	0.884	1.017	2.767	6.564	0	0	0.024	0.092	10.863	11.092	10.842	11.169	10.869	11.138
	0.7	88.275	116.801	0.002	0.009	0.84	1.251	2.361	5.691	0	0	0.035	0.081	10.603	10.814	10.561	10.856	10.575	10.86
	0.8	84.937	108.155	0	0	0.912	1.124	3.762	7.213	0	0	0.025	0.04	10.066	10.564	9.964	10.381	10.034	10.422
	0.9	83.932	96.221	0	0	0.781	1.18	4.207	10.818	0	0	0.03	0.062	9.039	9.599	9.347	9.989	9.191	9.615
150	0.6	87.157	100.618	0	0	0.599	0.759	6.623	9.635	0	0	0.082	0.126	22.663	23.141	22.515	23.06	22.424	22.87
	0.7	88.804	100.072	0	0	0.602	0.677	6.866	10.731	0	0	0.091	0.113	21.9	22.214	21.759	22.277	21.755	22.386
	0.8	86.592	98.456	0	0	0.583	0.745	6.783	9.836	0	0	0.089	0.161	21.435	21.862	21.38	21.98	21.633	22.23
	0.9	84.431	106.413	0.003	0.005	0.593	0.687	6.664	9.043	0	0	0.08	0.147	20.213	20.688	20.404	21.097	20.466	21.138
200	0.6	83.977	98.545	0	0	0.432	0.524	8.243	15.256	0	0	0.117	0.165	38.573	39.729	38.005	39.17	37.532	38.825
	0.7	93.933	104.681	0	0	0.435	0.53	8.561	16.389	0	0	0.117	0.183	37.504	38.735	37.118	37.564	37.252	37.581
	0.8	96.236	105.467	0.002	0.011	0.447	0.577	8.572	16.24	0	0	0.114	0.179	37.424	38.548	37.275	38.61	37.213	38.205
	0.9	90.333	100.959	0	0	0.414	0.476	8.057	16.283	0	0	0.132	0.189	35.678	36.28	35.481	36.42	36.527	37.766

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	F. Ahmadizar and L. Hosseini, Bi-criteria single machine scheduling with a time-dependent learning effect and release times, Applied Mathematical Modelling, 36 (2012), 6203-6214. doi: 10.1016/j.apm.2012.02.002.
[2]	D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315-329. doi: 10.1016/j.ejor.2007.05.040.
[3]	T.C.E. Cheng, W.-H. Kuo and D.-L. Yang, Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position, Information Sciences, 221 (2013), 490-500. doi: 10.1016/j.ins.2012.09.001.
[4]	T.C.E. Cheng, W.-H. Kuo and D.-L. Yang, Scheduling with a position-weighted learning effect, Optimization Letters, 8 (2014), 293-306. doi: 10.1007/s11590-012-0574-5.
[5]	M. Cheng, P.-R. Tadikamall, J. Shang and B. Zhang, Single machine scheduling problems with exponentially time-dependent learning effects, Journal of Manufacturing Systems, 34 (2015), 60-65. doi: 10.1016/j.jmsy.2014.11.001.
[6]	C. Chu, Efficient heuristics to minimize total flow time with release dates, Operations Research Letters, 12 (1992), 321-330. doi: 10.1016/0167-6377(92)90092-H.
[7]	M.-I. Dessouky and J.-S. Deogun, Sequencing jobs with unequal ready times to minimize mean flow time, SIAM Journal on Computing, 10 (1981), 192-202. doi: 10.1137/0210014.
[8]	B. Haddar, M. Khemakhem, S. Hanafi and C. Wilbaut, A hybrid quantum particle swarm optimization for the multidimensional knapsack problem, Engineering Applications of Artificial Intelligence, 55 (2016), 1-13. doi: 10.1016/j.engappai.2016.05.006.
[9]	N. Hosseini and R. Tavakkoli-Moghaddam, Two meta-heuristics for solving a new two-machine flowshop scheduling problem with the learning effect and dynamic arrivals, The International Journal of Advanced Manufacturing Technology, 65(5) (2013), 771-786. doi: 10.1007/s00170-012-4216-y.
[10]	A. Janiak, M.-Y. Kovalyov and M. Lichtenstein, Strong NP-hardness of scheduling problems with learning or aging effect, Annals of Operations Research, 206 (2013), 577-583. doi: 10.1007/s10479-013-1364-x.
[11]	W.-H. Kuo, Single-machine group scheduling with time-dependent learning effect and position-based setup time learning effect, Annals of Operations Research, 196 (2012), 349-359. doi: 10.1007/s10479-012-1111-8.
[12]	W.-C. Lee, C.-C. Wu and P.-H. Hsu, A single-machine learning effect scheduling problem with release times, Omega, 38(1-2) (2010), 3-11. doi: 10.1016/j.omega.2009.01.001.
[13]	Y.-Y. Lu, F. Teng, and Z.-X. Feng, Scheduling jobs with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects, Asia-Pacific Journal of Operational Research, 32(4) (2015), 1550026. doi: 10.1142/S0217595915500268.
[14]	F. Marini and B. Walcza, Particle swarm optimization (PSO). A tutorial, Chemometrics and Intelligent Laboratory Systems, 149 (2015), 153-165. doi: 10.1016/j.chemolab.2015.08.020.
[15]	H. Melo and J. Watada, Gaussian-PSO with fuzzy reasoning based on structural learning for training a neural network, Neurocomputing, 172 (2016), 405-412. doi: 10.1016/j.neucom.2015.03.104.
[16]	Y.-P. Niu, L. Wan and J.-B. Wang, A note on scheduling jobs with extended sum-of-processing-times-based and position-based learning effect, Asia-Pacific Journal of Operational Research, 32 (2015), 1550001 (12 pages). doi: 10.1142/S0217595915500013.
[17]	I. Pan and S. Das, Fractional order fuzzy control of hybrid power system with renewable generation using chaotic PSO, SA Transactions, 62 (2016), 19-29. doi: 10.1016/j.isatra.2015.03.003.
[18]	R. Rudek, The single processor total weighted completion time scheduling problem with the sum-of-processing-time based learning model, Information Sciences, 199 (2012), 216-229. doi: 10.1016/j.ins.2012.02.043.
[19]	Y.-R. Shiau, M.-S. Tsai, W.-C. Lee and T.C.E. Cheng, Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time, Computers & Industrial Engineering, 87 (2015), 580-589. doi: 10.1016/j.cie.2015.05.032.
[20]	M.-R. Singh and S.-S. Mahapatra, A quantum behaved particle swarm optimization for flexible job shop scheduling, Computers & Industrial Engineering, 93 (2016), 36-44. doi: 10.1016/j.cie.2015.12.004.
[21]	L.-H. Sun, K. Cui, J.-H. Chen, J. Wang and X.-C. He, Some results of the worst-case analysis for flow shop scheduling with a learning effect, Annals of Operations Research, 211 (2013), 481-490. doi: 10.1007/s10479-013-1368-6.
[22]	J.-B. Wang and M.-Z. Wang, Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects, Annals of Operations Research, 191 (2011), 155-169. doi: 10.1007/s10479-011-0923-2.
[23]	J.-B. Wang and J.-J. Wang, Single-machine scheduling with precedence constraints and position-dependent processing times, Applied Mathematical Modelling, 37 (2013), 649-658. doi: 10.1016/j.apm.2012.02.055.
[24]	J.-J. Wang and B.-H. Zhang, Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects, Computers & Operations Research, 58 (2015), 24-31. doi: 10.1016/j.cor.2014.12.006.
[25]	C.-C. Wu, P.-H. Hsu, J.-C. Chen and N.-S. Wang, Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times, Computers & Operations Research, 38 (2011), 1025-1034. doi: 10.1016/j.cor.2010.11.001.
[26]	C.-C. Wu and C.-L. Liu, Minimizing the makespan on a single machine with learning and unequal release times, Computers & Industrial Engineering, 59 (2010), 419-424. doi: 10.1016/j.cie.2010.05.014.