Search Advanced

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 3: 3110-3126. doi: 10.3934/mbe.2022144
Previous Article Next Article
Research article

Due-window assignment scheduling with past-sequence-dependent setup times

  • Business School, Northwest Normal University, Lanzhou 730070, China

  • Academic Editor: Peng-Yeng Yin
  • Received: 29 September 2021 Revised: 02 January 2022 Accepted: 16 January 2022 Published: 19 January 2022

  • This article investigates the due-window assignment scheduling problem with setup times on a single machine, where setup times of jobs are past-sequence-dependent. Under common, slack and unrestricted due-window assignment methods, the goal is to determine the optimal job sequence and due-window such that the cost function (i.e., the weighted sum of earliness and tardiness, number of early and tardy jobs, due-window starting time and size) is minimized. We solve the problem optimally by introducing a polynomial time algorithm. An extension to the problem with learning and deterioration effects is also studied.

    Citation: Weiguo Liu, Xuyin Wang, Xiaoxiao Wang, Peizhen Zhao. Due-window assignment scheduling with past-sequence-dependent setup times[J]. Mathematical Biosciences and Engineering, 2022, 19(3): 3110-3126. doi: 10.3934/mbe.2022144

    Related Papers:

  • This article investigates the due-window assignment scheduling problem with setup times on a single machine, where setup times of jobs are past-sequence-dependent. Under common, slack and unrestricted due-window assignment methods, the goal is to determine the optimal job sequence and due-window such that the cost function (i.e., the weighted sum of earliness and tardiness, number of early and tardy jobs, due-window starting time and size) is minimized. We solve the problem optimally by introducing a polynomial time algorithm. An extension to the problem with learning and deterioration effects is also studied.


    加载中


    [1] C. Koulamas, G. J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent setup times, Eur. J. Oper. Res., 187 (2008), 1045–1049. https://doi.org/10.1016/j.ejor.2006.03.066 doi: 10.1016/j.ejor.2006.03.066
    [2] D. Biskup, J. Herrmann, Single-machine scheduling against due dates with past-sequence-dependent setup times, Eur. J. Oper. Res., 191 (2008), 587–592. https://doi.org/10.1016/j.ejor.2007.08.028 doi: 10.1016/j.ejor.2007.08.028
    [3] C. Koulamas, G. J. Kyparisis, New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives, Eur. J. Oper. Res., 278 (2019), 149–159. https://doi.org/10.1016/j.ejor.2019.04.022 doi: 10.1016/j.ejor.2019.04.022
    [4] W. H. Kuo, D. L. Yang, Single machine scheduling with past-sequence-dependent setup times and learning effects, Inf. Process. Lett., 102 (2007), 22–26. https://doi.org/10.1016/j.ipl.2006.11.002 doi: 10.1016/j.ipl.2006.11.002
    [5] X. R. Wang, J. B. Wang, W. J. Gao, X. Huang, Scheduling with past-sequence-dependent setup times and learning effects on a single machine, Int. J. Adv. Manuf. Technol., 48 (2010), 739–746. https://doi.org/10.1007/s00170-009-2308-0 doi: 10.1007/s00170-009-2308-0
    [6] V. Mani, P. C. Chang, S. H. Chen, Single-machine scheduling with past-sequence-dependent setup times and learning effects: a parametric analysis, Int. J. Syst. Sci., 42 (2011), 2097–2102. https://doi.org/10.1080/00207721003718436 doi: 10.1080/00207721003718436
    [7] H. M. Soroush, Scheduling in bicriteria single machine systems with past-sequence-dependent setup times and learning effects, J. Oper. Res. Soc., 65 (2014), 1017–1036. https://doi.org/10.1057/jors.2013.43 doi: 10.1057/jors.2013.43
    [8] L. Y. Wang, X. Huang, W. W. Liu, Y. B. Wu, J. B. Wang, Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times, RAIRO-Oper. Res., 55 (2021), 2747–2758. https://doi.org/10.1051/ro/2020117
    [9] A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, Eur. J. Oper. Res., 246 (2015), 345–378. https://doi.org/10.1016/j.ejor.2015.04.004 doi: 10.1016/j.ejor.2015.04.004
    [10] J. Pei, X. Liu, P. M. Pardalos, W. Fan, S. Yang, Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times, Ann. Oper. Res., 249 (2017), 175–195. https://doi.org/10.1007/s10479-015-1824-6 doi: 10.1007/s10479-015-1824-6
    [11] S. Muştu, T. Eren. The single machine scheduling problem with setup times under an extension of the general learning and forgetting effects, Optim. Lett., 15 (2020), 1327–1343. https://doi.org/10.1007/s11590-020-01641-9 doi: 10.1007/s11590-020-01641-9
    [12] M. D. Weerdt, R. Baart, L. He, Single-machine scheduling with release times, deadlines, setup times, and rejection, Eur. J. Oper. Res., 291 (2021), 629–639. https://doi.org/10.1016/j.ejor.2020.09.042 doi: 10.1016/j.ejor.2020.09.042
    [13] W. Wang, Single-machine due-date assignment scheduling with generalized earliness-tardiness penalties including proportional setup times, J. Appl. Math. Comput., 2021 (2021), 1–19. https://doi.org/10.1007/s12190-021-01555-4 doi: 10.1007/s12190-021-01555-4
    [14] A. Janiak, W. A. Janiak, T. Krysiak, T. Kwiatkowski, A survey on scheduling problems with due windows, Eur. J. Oper. Res., 242 (2015), 347–357. https://doi.org/10.1016/j.ejor.2014.09.043 doi: 10.1016/j.ejor.2014.09.043
    [15] G. A. Rolim, M. S. Nagano, Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review, Comput. Ind. Eng., 149 (2020), 106803. https://doi.org/10.1016/j.cie.2020.106803 doi: 10.1016/j.cie.2020.106803
    [16] S. D. Liman, S. S. Panwalkar, S. Thongmee, Common due window size and location determination in a single machine scheduling problem, J. Oper. Res. Soc., 49 (1998), 1007–1010. https://doi.org/10.1057/palgrave.jors.2600601 doi: 10.1057/palgrave.jors.2600601
    [17] X. Huang, N. Yin, W. W. Liu, J. B. Wang, Common due window assignment scheduling with proportional linear deterioration effects, Asia-Pac. J. Oper. Res., 37 (2020), 1950031. https://doi.org/10.1142/S0217595919500313 doi: 10.1142/S0217595919500313
    [18] J. B. Wang, Y. Hu, B. Zhang, Common due-window assignment for single-machine scheduling with generalized earliness/tardiness penalties and a rate-modifying activity, Eng. Optim., 53 (2021), 496–512. https://doi.org/10.1080/0305215X.2020.1740921 doi: 10.1080/0305215X.2020.1740921
    [19] J. B. Wang, B. Zhang, L. Li, D. Bai, Y. B. Feng, Due window assignment scheduling problems with position-dependent weights on a single machine, Eng. Optim., 52 (2020), 185–193. https://doi.org/10.1080/0305215X.2019.1577411 doi: 10.1080/0305215X.2019.1577411
    [20] D. Wang, Y. Yin, T. C. E. Cheng, A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times, Nav. Res. Logist., 64 (2017), 41–63. https://doi.org/10.1002/nav.21731 doi: 10.1002/nav.21731
    [21] Y. Yin, T. C. E. Cheng, C. C. Wu, S. R. Cheng, Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time, J. Oper. Res. Soc., 65 (2014), 1–13. https://doi.org/10.1057/jors.2012.161 doi: 10.1057/jors.2012.161
    [22] Y. Yin, D. Wang, T. C. E. Cheng, C. C. Wu, Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times, J. Oper. Res. Soc., 67 (2016), 1169–1183. https://doi.org/10.1057/jors.2016.14 doi: 10.1057/jors.2016.14
    [23] G. H. Hardy, J. E. Littlewood, G. Polya, Inequalities, Cambridge University Press, 1988. https://doi.org/10.1017/s0025557200143451
    [24] J. B. Wang, A note on scheduling problems with learning effect and deteriorating jobs, Int. J. Syst. Sci., 37 (2006), 827–833. https://doi.org/10.1080/00207720600879260 doi: 10.1080/00207720600879260
    [25] D. L. Yang, W. H. Kuo, Some scheduling problems with deteriorating jobs and learning effects, Comput. Ind. Eng., 58 (2010), 25–28. https://doi.org/10.1016/j.cie.2009.06.016 doi: 10.1016/j.cie.2009.06.016
    [26] S. Gawiejnowicz, Models and algorithms of time-dependent scheduling, Berlin: Springer, 2020. https://doi.org/10.1007/978-3-662-59362-2
    [27] A. Azzouz, M. Ennigrou, L. B. Said, Scheduling problems under learning effects: classification and cartography, Int. J. Prod. Res., 56 (2018), 1642–1661. https://doi.org/10.1080/00207543.2017.1355576 doi: 10.1080/00207543.2017.1355576
    [28] J. B. Wang, J. Xu, J. Yang, Bi-criterion optimization for flow shop with a learning effect subject to release dates, Complexity, 2018 (2018), 9149510. https://doi.org/10.1155/2018/9149510 doi: 10.1155/2018/9149510
    [29] B. Cheng, J. Duan, X. Zhu, M. Zhou, Optimizing batch operations with batch-position-dependent learning effect and aging effect, Comput. Ind. Eng., 157 (2021), 107325. https://doi.org/10.1016/j.cie.2021.107325 doi: 10.1016/j.cie.2021.107325
    [30] Y. Ma, C. Chu, C. Zuo, A survey of scheduling with deterministic machine availability constraints, Comput. Ind. Eng., 58 (2010), 199–211. https://doi.org/10.1016/j.cie.2009.04.014 doi: 10.1016/j.cie.2009.04.014
    [31] J. B. Wang, L. Li, Machine scheduling with deteriorating jobs and modifying maintenance activities, Comput. J., 61 (2018), 47–53. https://doi.org/10.1093/comjnl/bxx032 doi: 10.1093/comjnl/bxx032
    [32] J. B. Wang, Y. Hu, B. Zhang, Common due-window assignment for single-machine scheduling with generalized earliness/tardiness penalties and a rate-modifying activity, Eng. Optim., 53 (2021), 496–512. https://doi.org/10.1080/0305215X.2020.1740921 doi: 10.1080/0305215X.2020.1740921
  • Reader Comments
  • © 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Mathematical Biosciences and Engineering
3.9

Metrics

Article views(1806) PDF downloads(52) Cited by(4)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(3)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog