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.
Citation: |
[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. |