Search Advanced

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 9: 8923-8934. doi: 10.3934/mbe.2022414
Previous Article Next Article
Research article

Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times

  • School of Science, Shenyang Aerospace University, Shenyang, China

  • Academic Editor: Yang Kuang
  • Received: 15 April 2022 Revised: 04 June 2022 Accepted: 15 June 2022 Published: 20 June 2022

  • This article deals with common due-window assignment and single-machine scheduling with proportional-linear shortening processing times. Objective cost is a type of minmax, that is, the maximal cost among all processed jobs is minimized. Our goal is to determine an optimal schedule, the optimal starting time, and size of due-window that minimize the worst cost, which consist of four parts: earliness, tardiness, starting time and length of the due-window. Optimal properties of the problem are given, and then an optimal polynomial algorithm is proposed to solve the problem.

    Citation: Xue Jia, Jing Xue, Shi-Yun Wang, Ji-Bo Wang. Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times[J]. Mathematical Biosciences and Engineering, 2022, 19(9): 8923-8934. doi: 10.3934/mbe.2022414

    Related Papers:

  • This article deals with common due-window assignment and single-machine scheduling with proportional-linear shortening processing times. Objective cost is a type of minmax, that is, the maximal cost among all processed jobs is minimized. Our goal is to determine an optimal schedule, the optimal starting time, and size of due-window that minimize the worst cost, which consist of four parts: earliness, tardiness, starting time and length of the due-window. Optimal properties of the problem are given, and then an optimal polynomial algorithm is proposed to solve the problem.


    加载中


    [1] Y. Y. Lu, Research on no-idle permutation flowshop scheduling with time-dependent learning effect and deteriorating jobs, Appl. Math. Modell., 40 (2016), 3447–3450. https://doi.org/10.1016/j.apm.2015.09.081 doi: 10.1016/j.apm.2015.09.081
    [2] F. Liu, J. Yang, Y. Y. Lu, Solution algorithms for single-machine group scheduling with ready times and deteriorating jobs, Eng. Optim., 51 (2019), 862–874. https://doi.org/10.1080/0305215X.2018.1500562 doi: 10.1080/0305215X.2018.1500562
    [3] S. Gawiejnowicz, Models and Algorithms of Time-Dependent Scheduling, Springer-Berlin, 2020. https://doi.org/10.1007/978-3-662-59362-2
    [4] X. Huang, Bicriterion scheduling with group technology and deterioration effect, J. Appl. Math. Comput., 60 (2019), 455–464. https://doi.org/10.1007/s12190-018-01222-1 doi: 10.1007/s12190-018-01222-1
    [5] D. W. Li, X. W. Lu, Parallel-batch scheduling with deterioration and rejection on a single machine, Appl. Math. J. Chin. Univ., 35 (2020), 141–156. https://doi.org/10.1007/s11766-020-3624-2 doi: 10.1007/s11766-020-3624-2
    [6] X. X. Liang, M. Liu, Y. B. Feng, J. B. Wang, L. S. Wen, Solution algorithms for single-machine resource allocation scheduling with deteriorating jobs and group technology, Eng. Optim., 52 (2020), 1184–1197. https://doi.org/10.1080/0305215X.2019.1638920 doi: 10.1080/0305215X.2019.1638920
    [7] X. Huang, N. Yin, W. W. Liu, J. B. Wang, Common due window assignment scheduling with proportional linear deterioration effects, Asia-Pacific J. Oper. Res., 37 (2020), 1950031. https://doi.org/10.1142/S0217595919500313 doi: 10.1142/S0217595919500313
    [8] G. Mosheiov, A common due-date assignment problem on parallel identical machines, Comput. Oper. Res., 28 (2001), 719–732. https://doi.org/10.1016/S0305-0548(99)00127-6 doi: 10.1016/S0305-0548(99)00127-6
    [9] G. Mosheiov, A. Sarig, Minmax scheduling problems with a common due-window, Comput. Oper. Res., 36 (2009), 1886–1892. https://doi.org/10.1016/j.cor.2008.06.001 doi: 10.1016/j.cor.2008.06.001
    [10] E. Gerstl, G. Mosheiov, Minmax due-date assignment with a time window for acceptable lead-times, Ann. Oper. Res., 211 (2013), 167–177. https://doi.org/10.1007/s10479-013-1458-5 doi: 10.1007/s10479-013-1458-5
    [11] G. Mosheiov, A due-window determination in minmax scheduling problems, INFOR: Inf. Syst. Oper. Res., 39 (2001), 107–123. https://doi.org/10.1080/03155986.2001.11732429 doi: 10.1080/03155986.2001.11732429
    [12] B. Mor, Minmax scheduling problems with common due-date and completion time penalty, J. Comb. Optim., 38 (2019), 50–71. https://doi.org/10.1007/s10878-018-0365-8 doi: 10.1007/s10878-018-0365-8
    [13] G. Mosheiov, A. Sarig, V. Strusevich, Minmax scheduling and due-window assignment with position-dependent processing times and job rejection, 4OR, 18 (2020), 439–456. https://doi.org/10.1007/s10288-019-00418-w doi: 10.1007/s10288-019-00418-w
    [14] W. Liu, X. Hu, X. Y. Wang, Single machine scheduling with slack due dates assignment, Eng. Optim., 49 (2017), 709–717. https://doi.org/10.1080/0305215X.2016.1197611 doi: 10.1080/0305215X.2016.1197611
    [15] Y. Q. Yin, D. J. Wang, T. C. E. Cheng, Due Date-Related Scheduling with Two Agents, Springer-Berlin, 2020. https://doi.org/10.1007/978-981-15-2105-8
    [16] G. A. Rolin, 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
    [17] X. Sun, X. N. Geng, T. Liu, Due-window assignment scheduling in the proportionate flow shop setting, Ann. Oper. Res., 292 (2020), 113–131. https://doi.org/10.1007/s10479-020-03653-1 doi: 10.1007/s10479-020-03653-1
    [18] S. Zhao, Resource allocation flowshop scheduling with learning effect and slack due window assignment, J. Ind. Manage. Optim., 17 (2021), 2817–2835. https://doi.org/10.3934/jimo.2020096 doi: 10.3934/jimo.2020096
    [19] W. Liu, X. Wang, X. Wang, P. Zhao, Due-window assignment scheduling with past-sequence-dependent setup times, Math. Biosci. Eng., 19 (2022), 3110–3126. https://doi.org/10.3934/mbe.2022144 doi: 10.3934/mbe.2022144
    [20] X. Wang, W. Liu, L. Li, P. Zhao, R. Zhang, Due date assignment scheduling with positional-dependent weights and proportional setup times, Math. Biosci. Eng., 19 (2022), 5104–5119. https://doi.org/10.3934/mbe.2022238 doi: 10.3934/mbe.2022238
    [21] K. I. J. Ho, J. Y. T. Leung, W. D. Wei, Complexity of scheduling tasks with time-dependent execution times, Inf. Process. Lett., 48 (1993), 315–320. https://doi.org/10.1016/0020-0190(93)90175-9 doi: 10.1016/0020-0190(93)90175-9
    [22] J. B. Wang, Z. Q. Xia, Scheduling jobs under decreasing linear deterioration, Inf. Process. Lett., 94 (2005), 63–69. https://doi.org/10.1016/j.ipl.2004.12.018 doi: 10.1016/j.ipl.2004.12.018
    [23] C. C. Wu, W. C. Lee, M. J. Liou, Single-machine scheduling with two competing agents and learning consideration, Inf. Sci., 251 (2013), 136–149. https://doi.org/10.1016/j.ins.2013.06.054 doi: 10.1016/j.ins.2013.06.054
    [24] C. C. Wu, Y. Yin, S. R. Cheng, Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions, J. Oper. Res. Soc., 64 (2013), 147–156. https://doi.org/10.1057/jors.2012.46 doi: 10.1057/jors.2012.46
    [25] W. C. Yeh, P. J. Lai, W. C. Lee, M. C. Chuang, Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects, Inf. Sci., 269 (2014), 142–158. https://doi.org/10.1016/j.ins.2013.10.023 doi: 10.1016/j.ins.2013.10.023
    [26] J. B. Wang, D. Y. Lv, J. Xu, P. Ji, F. Li, Bicriterion scheduling with truncated learning effects and convex controllable processing times, Int. Trans. Oper. Res., 28 (2021), 1573–1593. https://doi.org/10.1111/itor.12888 doi: 10.1111/itor.12888
    [27] D. Y. Lv, J. B. Wang, Study on resource-dependent no-wait flow shop scheduling with different due-window assignment and learning effects, Asia-Pacific J. Oper. Res., 38 (2021), 2150008. https://doi.org/10.1142/S0217595921500081 doi: 10.1142/S0217595921500081
  • 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(1325) PDF downloads(48) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(1)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog