Due-window assignment scheduling with learning and deterioration effects

Shan-Shan Lin

doi:10.3934/jimo.2021081

Article Contents

2022, Volume 18, Issue 4: 2567-2578. Doi: 10.3934/jimo.2021081

This issue Previous Article Weakening convergence conditions of a potential reduction method for tensor complementarity problems Next Article A full-modified-Newton step

$ O(n) $

infeasible interior-point method for the special weighted linear complementarity problem

Due-window assignment scheduling with learning and deterioration effects

Shan-Shan Lin^,

School of Business and Management, Fujian Jiangxia University, Fuzhou 350108, China

^* Corresponding author: 1257290990@qq.com
^* Corresponding author: 1257290990@qq.com

Received: August 31, 2020

Revised: January 31, 2021

Published: July 2022

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

Abstract

This paper considers single machine due-window assignment scheduling problems with position-dependent weights. Under the learning and deterioration effects of jobs processing times, our goal is to minimize the weighted sum of earliness-tardiness, starting time of due-window, and due-window size, where the weights only depends on their position in a sequence (i.e., position-dependent weights). Under common due-window (CONW), slack due-window (SLKW) and different due-window (DIFW) assignments, we show that these problems remain polynomial-time solvable.

Keywords:

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

Citation:

Full Text(HTML)

Table 1. Values $\Omega_{r}a_{i}r^{\beta_{i}}$ of Example 1 (optimal values in bold)

${J_i\backslash r}$	1	2	3	4	5	6	7	8
$J_1$	58.5816	70.5534	71.6796	60.2931	51.6071	44.6619	35.1836	19.9634
$J_2$	66.9504	80.0754	81.0244	67.9577	58.0379	50.1358	39.4350	22.3457
$J_3$	133.9008	156.8550	156.7951	130.3788	110.6044	95.0240	74.3975	41.9887
$J_4$	41.8440	47.6768	46.8919	38.5456	32.4088	27.6412	21.5082	12.0742
$J_5$	75.3192	89.4626	90.1566	75.3999	64.2502	55.4012	43.5094	24.6216
$J_6$	92.0568	115.5777	120.3143	102.9641	89.3186	78.1486	62.1357	35.5397
$J_7$	167.3760	204.3950	209.3484	177.1090	152.2722	132.2612	104.5140	59.4604
$J_8$	108.7944	125.6902	124.6273	103.0361	87.0194	74.4893	58.1407	32.7261

| Show Table

DownLoad: CSV

Table 2. Summary of Results

problem	complexity	reference
$1\|P_i^A = a_ir^{\beta_i}+bs_i\|C_{\max}$	$O(n^3)$	Yang and Kuo [32]
$1\|P_i^A = a_ir^{\beta}+bs_i\|C_{\max}$	$O(n\log n)$	Yang and Kuo [32]
$1\|P_i^A = a_ir^{\beta_i}+bs_i\|\sum\limits_{i = 1}^n C_{i}$	$O(n^3)$	Yang and Kuo [32]
$1\|P_i^A = a_ir^{\beta}+bs_i\|\sum\limits_{i = 1}^n C_{i}$	$O(n\log n)$	Yang and Kuo [32]
$1\|P_i^A = a_ir^{\beta_i}+bs_i\|\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|C_{i}-C_j\|$	$O(n^3)$	Yang and Kuo [32]
$1\|P_i^A = a_ir^{\beta}+bs_i\|\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|C_{i}-C_j\|$	$O(n\log n)$	Yang and Kuo [32]
$1\|P_i^A = a_ir^{\beta_i}+bs_i\|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|C_{i}-C_j\|$	$O(n^3)$	Huang et al. [5]
$1\|P_i^A = a_ir^{\beta_i}+bs_i\|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|W_{i}-W_j\|$	$O(n^3)$	Huang et al. [5]
$1\|P_i^A = a_ir^{\beta}+bs_i\|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|C_{i}-C_j\|$	$O(n\log n)$	Huang et al. [5]
$1\|P_i^A = a_ir^{\beta}+bs_i\|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|W_{i}-W_j\|$	$O(n\log n)$	Huang et al. [5]
$Pm\|P_i^A = a_ir^{\beta_i}+bs_i\|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|C_{i}-C_j\|$	$O(n^{m+2})$	Huang et al. [5]
$Pm\|P_i^A = a_ir^{\beta_i}+bs_i\|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|W_{i}-W_j\|$	$O(n^{m+2})$	Huang et al. [5]
$Rm\|P_i^A = a_ir^{\beta_i}+bs_i\|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|C_{i}-C_j\|$	$O(n^{m+2})$	Huang et al. [5]
$Rm\|P_i^A = a_ir^{\beta_i}+bs_i\|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n \|W_{i}-W_j\|$	$O(n^{m+2})$	Huang et al. [5]
$1\|P_i^A = (a_i+bs_i)r^{\beta}\|C_{\max}$	$O(n\log n)$	Wang [18]
$1\|P_i^A = (a_i+bs_i)r^{\beta}\|\sum\limits_{i = 1}^nC_{i}$	$O(n\log n)$	Wang [18]
$1\|CONW,P_i^A = (a_i+bs_i)r^{\beta}\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$	$O(n\log n)$	Wang and Wang [24]
$1\|SLKW,P_i^A = (a_i+bs_i)r^{\beta}\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$	$O(n\log n)$	Wang et al. [20]
$1\|DIFW,P_i^A = (a_i+bs_i)r^{\beta}\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_j'+\vartheta D_j\right)$	$O(n\log n)$	Wang et al. [20]
$1\|CONW,P_i^A = a_ir^{\beta_i}+bs_i\|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$	$O(n^3)$	Theorem 1
$1\|CONW,P_i^A = a_ir^{\beta}+bs_i\|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$	$O(n\log n)$	Theorem 2
$1\|SLKW,P_i^A = a_ir^{\beta_i}+bs_i\|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}q'+\eta_{n+1}D$	$O(n^3)$	Theorem 3
$1\|SLKW,P_i^A = a_ir^{\beta}+bs_i\|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$	$O(n\log n)$	Theorem 4
$1\|DIFW,P_i^A = a_ir^{\beta_i}+bs_i\|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$	$O(n^3)$	Theorem 5
$1\|DIFW,P_i^A = a_ir^{\beta}+bs_i\|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$	$O(n\log n)$	Theorem 6
$1\|CONW,P_i^A = a_ir^{\beta_i}+bs_i\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$	$O(n^3)$	Theorem 7
$1\|CONW,P_i^A = a_ir^{\beta}+bs_i\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$	$O(n\log n)$	Theorem 8
$1\|SLKW,P_i^A = a_ir^{\beta_i}+bs_i\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$	$O(n^3)$	Theorem 9
$1\|SLKW,P_i^A = a_ir^{\beta}+bs_i\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$	$O(n\log n)$	Theorem 10
$1\|DIFW,P_i^A = a_ir^{\beta_i}+bs_i\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_{\pi(i)}'+\vartheta D_{\pi(i)}\right)$	$O(n^3)$	Theorem 11
$1\|DIFW,P_i^A = a_ir^{\beta}+bs_i\|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_{\pi(i)}'+\vartheta D_{\pi(i)}\right)$	$O(n\log n)$	Theorem 12
$1\|CONW,P_i^A = (a_i+bs_i)r^{\beta}\|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$	$O(n\log n)$	Theorem 13
$1\|SLKW,P_i^A = (a_i+bs_i)r^{\beta}\|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}q'+\eta_{n+1}D$	$O(n\log n)$	Theorem 14
$1\|DIFW,P_i^A = (a_i+bs_i)r^{\beta}\|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$	$O(n\log n)$	Theorem 15
$m$ is the number of machines, $\theta_1\geq0, \theta_2\geq0$ are given constants $W_i = C_i-P_i^A$ is the waiting time of job $J_i$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, International Journal of Production Research, 56 (2018), 1642-1661.
[2]	S. Gawiejnowicz, Models and Algorithms of Time-Dependent Scheduling, Springer-Verlag Berlin Heidelberg, 2020.
[3]	G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities (2nd ed.), Cambridge: Cambridge University Press, 1988.
[4]	X. Huang, Bicriterion scheduling with group technology and deterioration effect, J. Appl. Math. Comput., 60 (2019), 455-464. doi: 10.1007/s12190-018-01222-1.
[5]	X. Huang, M.-Z. Wang and P. Ji, Parallel machines scheduling with deteriorating and learning effects, Optim. Lett., 8 (2014), 493-500. doi: 10.1007/s11590-012-0490-8.
[6]	A. Janiak, W. A. Janiak, T. Krysiak and T. Kwiatkowski, A survey on scheduling problems with due windows, European J. Oper. Res., 242 (2015), 347-357. doi: 10.1016/j.ejor.2014.09.043.
[7]	M. Ji, K. Chen, J. Ge and T. C. E. Cheng, Group scheduling and job-dependent due window assignment based on a common flow allowance, Computers & Industrial Engineering, 68 (2014), 35-41.
[8]	W.-C. Lee, A note on deteriorating jobs and learning in single-machine scheduling problems, International Journal of Business and Economics, 3 (2004), 83-89.
[9]	G. Li, M.-L. Luo, W.-J. Zhang and X.-Y. Wang, Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation, International Journal of Production Research, 53 (2015), 1228-1241.
[10]	X.-X. Liang, B. Zhang, J.-B. Wang, N. Yin and X. Hang, Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects, J. Appl. Math. Comput., 61 (2019), 373-388. doi: 10.1007/s12190-019-01255-0.
[11]	S. D. Liman, S. S. Panwalkar and S. Thongmee, Common due window size and location determination in a single machine scheduling problem, Journal of the Operational Research Society, 49 (1998), 1007-1010.
[12]	J. Liu, Y. Wang and X. Min, Single-machine scheduling with common due-window assignment for deteriorating jobs, Journal of the Operational Research Society, 65 (2014), 291-301.
[13]	Y.-Y. Lu, Research on no-idle permutation flowshop scheduling with time-dependent learning effect and deteriorating jobs, Appl. Math. Model., 40 (2016), 3447-3450. doi: 10.1016/j.apm.2015.09.081.
[14]	B. Mor and G. Mosheiov, Scheduling a deteriorating maintenance activity and due-window assignment, Comput. Oper. Res., 57 (2015), 33-40. doi: 10.1016/j.cor.2014.11.016.
[15]	G. Mosheiov and D. Oron, Job-dependent due-window assignment based on a common flow allowance, Foundations of Computing and Decision Sciences, 35 (2010), 185-195.
[16]	D. A. Nembhard and N. Osothsilp, Task complexity effects on between-individual learning/forgetting variability, International Journal of Industrial Ergonomics, 29 (2002), 297-306.
[17]	H. Soleimani, H. Ghaderi, P.-W. Tsai, N. Zarbakhshnia and M. Maleki, Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization, Journal of Cleaner Production, 249 (2020), 119428.
[18]	J.-B. Wang, A note on scheduling problems with learning effect and deteriorating jobs, Internat. J. Systems Sci., 37 (2006), 827-833. doi: 10.1080/00207720600879260.
[19]	J.-B. Wang, Y. Hu and B. Zhang, Common due-window assignment for single-machine schedulingwith generalized earliness/tardiness penalties and a rate-modifying activity, Eng. Optim., 53 (2021), 496-512. doi: 10.1080/0305215X.2020.1740921.
[20]	J.-B. Wang, L. Liu and C. Wang, Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 37 (2013), 8394-8400. doi: 10.1016/j.apm.2013.03.041.
[21]	J.-B. Wang, F. Liu and J.-J. Wang, Research on $m$-machine flow shop scheduling with truncated learning effects, Int. Trans. Oper. Res., 26 (2019), 1135-1151. doi: 10.1111/itor.12323.
[22]	J.-B. Wang, D.-Y. Lv, J. Xu, P. Ji and F. Li, Bicriterion scheduling with truncated learning effects and convex controllable processing times, Int. Trans. Oper. Res., 28 (2021), 1573-1593. doi: 10.1111/itor.12888.
[23]	L.-Y. Wang, D.-Y. Lv, B. Zhang, W.-W. Liu and J.-B. Wang, Optimization for due-window assignment scheduling with position-dependent weights, Discrete Dyn. Nat. Soc., 2020 (2020), 9746583, 7 pp. doi: 10.1155/2020/9746538.
[24]	J.-B. Wang and C. Wang, Single-machine due-window assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 35 (2011), 4017-4022. doi: 10.1016/j.apm.2011.02.023.
[25]	D. Wang, Y. Yin and T. C. E. Cheng, A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times, Naval Res. Logist., 64 (2017), 41-63. doi: 10.1002/nav.21731.
[26]	D. Wang, Y. Yu, H. Qiu, Y. Yin and T. C. E. Cheng, Two-agent scheduling with linear resource-dependent processing times, Naval Res. Logist., 67 (2020), 573-591. doi: 10.1002/nav.21936.
[27]	J.-B. Wang, B. Zhang and H. He, A unified analysis for scheduling problems with variable processing times, J. Ind. Manag. Optim., (2021). doi: 10.3934/jimo.2021008.
[28]	J.-B. Wang, B. Zhang, L. Li, D. Bai and Y.-B. Feng, Due window assignment scheduling problems with position-dependent weights on a single machine, Eng. Optim., 52 (2020), 185-193. doi: 10.1080/0305215X.2019.1577411.
[29]	Y.-B. Wu, L. Wan and X.-Y. Wang, Study on due-window assignment scheduling based on common flow allowance, International Journal of Production Economics, 165 (2015), 155-157.
[30]	X. Xiong, P. Zhou, Y. Yin, T. C. E. Cheng and D. Li, An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines, Naval Res. Logist., 66 (2019), 502-516. doi: 10.1002/nav.21863.
[31]	P. Yan, J.-B. Wang and L.-Q. Zhao, Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects, J. Ind. Manag. Optim., 15 (2019), 1117-1131. doi: 10.3934/jimo.2018088.
[32]	D.-L. Yang and W.-H. Kuo, Some scheduling problems with deteriorating jobs and learning effects, Computer & Industrial Engineering, 58 (2010), 25–28. 1117–1131.
[33]	D.-L. Yang, C.-J. Lai and S.-J. Yang, Scheduling problems with multiple common due windows assignment and controllable processing times on a single machine, International Journal of Production Economics, 150 (2014), 96-103.
[34]	Y. Yin, T. C. E. Cheng, C.-C. Wu and S.-R. Cheng, Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time, Journal of the Operational Research Society, 65 (2014), 1-13.
[35]	Y. Yin, D. Wang, T. C. E. Cheng and C.-C. Wu, Bi-criterion single-machine scheduling and due window assignment with common flow allowances and resource allocation, Journal of the Operational Research Society, 67 (2016), 1169-1183.
[36]	Y. Yin, D.-J. Wang, C.-C. Wu and T. C. E. Cheng, $CON/SLK$ due date assignment and scheduling on a single machine with two agents, Naval Res. Logist., 63 (2016), 416-429. doi: 10.1002/nav.21700.
[37]	Y. Yin, Y. Yang, D. Wang, T. C. E. Cheng and C.-C. Wu, Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents, Naval Res. Logist., 65 (2018), 393-409. doi: 10.1002/nav.21813.
[38]	X. Zhang, Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon, J. Ind. Manag. Optim., 16 (2020), 231-244. doi: 10.3934/jimo.2018148.
[39]	S. Zhao, Resource allocation flowshop scheduling with learning effect and slack due window assignment, J. Ind. Manag. Optim., (2020). doi: 10.3934/jimo.2020096.