Article Contents

2024, Volume 20, Issue 1: 313-324. Doi: 10.3934/jimo.2023079

This issue Previous Article A modified four-term extension of the Dai–Liao conjugate gradient method Next Article An improved inertial projection method for solving convex constrained monotone nonlinear equations with applications

Due-window assignment scheduling with job-rejection, truncated learning effects and setup times

Business School, Northwest Normal University, Lanzhou 730070, China

^*Corresponding authors: Weiguo Liu
^*Corresponding authors: Weiguo Liu

Received: February 2023

Revised: April 2023

Early access: June 2023

Published: January 2024

This research was supported by the National Natural Science Regional Foundation of China (72061029 and 71861031)

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

This paper investigates the single-machine due-window assignment scheduling with truncated learning effects and past-sequence-dependent setup times simultaneously. The scheduler has the option of job-rejection, i.e., some jobs are processed and the other jobs are rejected. Under three (i.e., common, slack and different) due-window assignment methods, our goal is to minimize the sum of a general earliness-tardiness cost (i.e., the weighted sum of earliness-tardiness, number of early and tardy jobs, starting time and size of due-window) and a total rejection cost. Some optimal properties of the problem are provided, and we demonstrate that the problem is polynomially solvable.

Keywords:

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

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, European Journal of Operational Research, 246 (2015), 345-378. doi: 10.1016/j.ejor.2015.04.004.
[2]	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.
[3]	D. Biskup and J. Herrmann, Single-machine scheduling against due dates with past-sequence-dependent setup times, European Journal of Operational Research, 191 (2008), 587-592. doi: 10.1016/j.ejor.2007.08.028.
[4]	X. Huang, N. Yin, W.-W. Liu and J.-B. Wang, Common due window assignment scheduling with proportional linear deterioration effects, Asia-Pacific Journal of Operational Research, 37 (2020), 1950031. doi: 10.1142/S0217595919500313.
[5]	A. Janiak, W.-A. Janiak, T. Krysiak and T. Kwiatkowski, A survey on scheduling problems with due windows, European Journal of Operational Research, 242 (2015), 347-357. doi: 10.1016/j.ejor.2014.09.043.
[6]	X. Jia, D.-Y. Lv, Y. Hu, J.-B. Wang, Z. Wang and E. Wang, Slack due-window assignment scheduling problem with deterioration effects and a deteriorating maintenance activity, Asia-Pacific Journal of Operational Research, 39 (2022), 2250005. doi: 10.1142/S0217595922500051.
[7]	C. Koulamas and G.-J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent setup times, European Journal of Operational Research, 187 (2008), 1045-1049. doi: 10.1016/j.ejor.2006.03.066.
[8]	C. Koulamas and G.-J. Kyparisis, New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives, European Journal of Operational Research, 278 (2019), 149-159. doi: 10.1016/j.ejor.2019.04.022.
[9]	S.-S. Li, R.-X. Chen, Q. Feng and C.-W. Jiao, Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection, Journal of Combinatorial Optimization, 38 (2019), 957-971. doi: 10.1007/s10878-019-00429-7.
[10]	W. Liu, X. Wang, X. Wang and P. Zhao, Due-window assignment scheduling with past-sequence-dependent setup times, Mathematical Biosciences and Engineering, 19 (2022), 3110-3126. doi: 10.3934/mbe.2022144.
[11]	D.-Y. Lv and J.-B. Wang, Study on resource-dependent no-wait flow shop scheduling with different due-window assignment and learning effects, Asia-Pacific Journal of Operational Research, 38 (2021), 2150008. doi: 10.1142/S0217595921500081.
[12]	H. Nian and Z. Mao, Single-machine scheduling with job rejection, deteriorating effects, and deteriorating maintenance activities, Mathematical Problems in Engineering, 2013 (2013), 389120. doi: 10.1155/2013/389120.
[13]	J. Pei, Y. Zhou, P. Yan and P.-M. Pardalos, A concise guide to scheduling with learning and deteriorating effects, International Journal of Production Research, 61 (2023), 2010-2031.
[14]	J. Qian and H. Han, Improved algorithms for proportionate flow shop scheduling with due-window assignment, Annals of Operations Research, 309 (2022), 249-258. doi: 10.1007/s10479-021-04414-4.
[15]	Y. Shabtay and N. Gaspar, Two-machine flow-shop scheduling with rejection, Computers & Operations Research, 39 (2012), 1097-1096.
[16]	Y. Shabtay, N. Gaspar and M. Kaspi, A survey on offline scheduling with rejection, Journal of Scheduling, 16 (2013), 3-28. doi: 10.1007/s10951-012-0303-z.
[17]	H.-M. Soroush, Scheduling in bicriteria single machine systems with past-sequence-dependent setup times and learning effects, Journal of the Operational Research Society, 65 (2014), 1017-1036.
[18]	X. Sun, X.-N. Geng and T. Liu, Due-window assignment scheduling in the proportionate flow shop setting, Annals of Operations Research, 292 (2020), 113-131. doi: 10.1007/s10479-020-03653-1.
[19]	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 Research Logistics, 64 (2017), 41-63. doi: 10.1002/nav.21731.
[20]	D. Wang, Y. Yin and M. Liu, Bicriteria scheduling problems involving job rejection, controllable processing times and rate-modifying activity, International Journal of Production Research, 54 (2016), 3691-3705.
[21]	J.-B. Wang, Y. Hu and B. Zhang, Common due-window assignment for single-machine scheduling with generalized earliness/tardiness penalties and a rate-modifying activity, Engineering Optimization, 53 (2021), 496-512. doi: 10.1080/0305215X.2020.1740921.
[22]	J.-B. Wang, S.-H. Wang, K. Gao, M. Liu and X. Jia, Due-window assignment methods and scheduling with generalized positional-dependent weights, Asia-Pacific Journal of Operational Research, 39 (2022), 2250028. doi: 10.1142/S0217595922500282.
[23]	J.-B. Wang, J.-X. Xu, F. Guo and M. Liu, Single-machine scheduling problems with job rejection, deteriorating effects and past-sequence-dependent setup times, Engineering Optimization, 54 (2022), 471-486.
[24]	J.-B. Wang, L.-H. Zhang, Z.-G. Lv, D.-Y. Lv, X.-N. Geng and X. Sun, Heuristic and exact algorithms for single-machine scheduling problems with general truncated learning effects, Computational and Applied Mathematics, 41 (2022), 23 pp. doi: 10.1007/s40314-022-02133-5.
[25]	L.-Y. Wang, X. Huang, W.-W. Liu, Y.-B. Wu and J.-B. Wang, Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times, RAIRO-Operations Research, 55 (2021), S2747-S2758. doi: 10.1051/ro/2020117.
[26]	S.-H. Wang, D.-Y. Lv and J.-B. Wang, Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect, Journal of Industrial and Management Optimization, 19 (2023), 2824-2837. doi: 10.3934/jimo.2022066.
[27]	W. Wang, Single-machine due-date assignment scheduling with generalized earliness/tardiness penalties including proportional setup times, Journal of Applied Mathematics and Computing, 68 (2022), 1013-1031. doi: 10.1007/s12190-021-01555-4.
[28]	X.-R. Wang, J. Jin, J.-B. Wang and P. Ji, Single machine scheduling with truncated job-dependent learning effect, Optimization Letters, 8 (2014), 669-677. doi: 10.1007/s11590-012-0579-0.
[29]	X. Wang, W. Liu, L. Li, P. Zhao and R. Zhang, Due date assignment scheduling with positional-dependent weights and proportional setup times, Mathematical Biosciences and Engineering, 19 (2022), 5104-5119. doi: 10.3934/mbe.2022238.
[30]	X.-R. Wang, J.-B. Wang, W.-J. Gao and X. Huang, Scheduling with past-sequence-dependent setup times and learning effects on a single machine, International Journal of Advanced Manufacturing Technology, 48 (2010), 739-746.
[31]	Y.-C. Wang, S.-H. Wang and J.-B. Wang, Resource allocation scheduling with position-dependent weights and generalized earliness-tardiness cost, Mathematics, 11 (2023), 222.
[32]	W. Wu, D.-Y. Lv and J.-B. Wang, Two due-date assignment scheduling with location-dependent weights and a deteriorating maintenance activity, Systems, 11 (2023), 150.
[33]	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.
[34]	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.
[35]	X. Zhang, W. Lin, W. Wu and C. Wu, Single-machine common/slack due window assignment problems with linear decreasing processing times, Engineering Optimization, 49 (2017), 1388-1400. doi: 10.1080/0305215X.2016.1248180.
[36]	S. Zhao, Resource allocation flowshop scheduling with learning effect and slack due window assignment, Journal of Industrial and Management Optimization, 17 (2021), 2817-2835. doi: 10.3934/jimo.2020096.
[37]	S. Zhao, Scheduling jobs with general truncated learning effects including proportional setup times, Computational and Applied Mathematics, 41 (2022), 25 pp. doi: 10.1007/s40314-022-01851-0.