\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Due-window assignment scheduling with learning and deterioration effects

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
  • [1] A. AzzouzM. 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. HardyJ. E. Littlewood and  G. PólyaInequalities (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. HuangM.-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. JaniakW. A. JaniakT. 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. JiK. ChenJ. 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. LiM.-L. LuoW.-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. LiangB. ZhangJ.-B. WangN. 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. LimanS. 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. LiuY. 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. WangY. 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. WangL. 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. WangF. 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. WangD.-Y. LvJ. XuP. 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. WangY. 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. WangY. YuH. QiuY. 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. WangB. ZhangL. LiD. 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. WuL. 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. XiongP. ZhouY. YinT. 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. YanJ.-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. YangC.-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. YinT. C. E. ChengC.-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. YinD. WangT. 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. YinD.-J. WangC.-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. YinY. YangD. WangT. 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.
  • 加载中

Tables(2)

SHARE

Article Metrics

HTML views(605) PDF downloads(517) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return