We focus on a single-machine scheduling problem with common and slack due-window assignment methods. Both the job sequence and due-windows are decision variables to be determined by the decision maker. We consider the following performance criterion: the total weighted number of early and late jobs plus the total weighted of earliness, tardiness and due-window assignment cost, where the weights depend on the position in which a job is scheduled. Some properties are established, and it is shown that the problem can be solved in $O (n^{5})$ time, where $n$ is the number of jobs. The extensions of the model are to cases of general position-dependent processing times and time-dependent processing times.

Keywords:

References

Azzouz, A, M Ennigrou and LB Said (2018). Scheduling problems under learning effects: classification and cartography. International Journal of Production Research, 56(4), 1642–1661. Crossref, Web of Science, Google Scholar
Biskup, D (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1), 173–178. Crossref, Web of Science, Google Scholar
Brucker, P (2001). Scheduling Algorithms, 3rd edn. Berlin: Springer. Crossref, Google Scholar
Chen, R-X and S-S Li (2021). Proportionate flow shop scheduling with two competing agents to minimize weighted late work and weighted number of late jobs. Asia-Pacific Journal of Operational Research, 38(02), 2050046. Link, Web of Science, Google Scholar
Choi, B-C, M-J Park, KM Kim and Y Min (2021). A parallel machine scheduling problem maximizing total weighted early work. Asia-Pacific Journal of Operational Research, 38(6), 2150007. Link, Web of Science, Google Scholar
Gawiejnowicz, S (2020). Models and Algorithms of Time-dependent Scheduling, Berlin: Springer. Crossref, Google Scholar
Huang, X (2019). Bicriterion scheduling with group technology and deterioration effect. Journal of Applied Mathematics and Computing, 60(1–2), 455–464. Crossref, Web of Science, Google Scholar
Huang, X, N Yin, W-W Liu and J-B Wang (2020). Common due window assignment scheduling with proportional linear deterioration effects. Asia-Pacific Journal of Operational Research, 37(1), 1950031. Link, Web of Science, Google Scholar
Janiak, A, WA Janiak, T Krysiak and T Kwiatkowski (2015). A survey on scheduling problems with due windows. European Journal of Operational Research, 242(2), 347–357. Crossref, Web of Science, Google Scholar
Ji, P, G Li, Y Huo and J-B Wang (2014). Single-machine common flow allowance scheduling with job-dependent aging effects and a deteriorating maintenance activity. Optimization Letters, 8(4), 1389–1400. Crossref, Web of Science, Google Scholar
Ji, M, D Yao, Q Yang and TCE Cheng (2015). Single-machine common flow allowance scheduling with aging effect, resource allocation, and a rate-modifying activity. International Transactions in Operational Research, 22, 997–1015. Crossref, Web of Science, Google Scholar
Jia, X, D-Y Lv, Y Hu, J-B Wang, Z Wang and E Wang (2022). Slack due-window assignment scheduling problem with deterioration effects and a deteriorating maintenance activity. Asia-Pacific Journal of Operational Research, 39, 2250005, https://doi.org/10.1142/S0217595922500051. Link, Web of Science, Google Scholar
Jiang, C, D Zou, D Bai and J-B Wang (2020). Proportional flowshop scheduling with position-dependent weights. Engineering Optimization, 52(1), 37–52. Crossref, Web of Science, Google Scholar
Koulamas, C (2017). Common due date assignment with generalized earliness/tardiness penalties. Computers and Industrial Engineering, 109, 79–83. Crossref, Web of Science, Google Scholar
Liang, X-X, B Zhang, J-B Wang, N Yin and X Huang (2019). Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects. Journal of Applied Mathematics and Computing, 61, 373–388. Crossref, Web of Science, Google Scholar
Liu, W, X Hu and X-Y Wang (2017). Single machine scheduling with slack due dates assignment. Engineering Optimization, 49(4), 709–717. Crossref, Web of Science, Google Scholar
Liu, W and C Jiang (2020). Flow shop resource allocation scheduling with due date assignment, learning effect and position-dependent weights. Asia-Pacific Journal of Operational Research, 37, 2050014. Link, Web of Science, Google Scholar
Lu, Y-Y, G Li, Y-B Wu and P Ji (2014). Optimal due-date assignment problem with learning effect and resource-dependent processing times. Optimization Letters, 8(1), 113–127. Crossref, Web of Science, Google Scholar
Lv, D-Y and J-B Wang (2021a). Study on proportionate flowshop scheduling with due-date assignment and position-dependent weights. Optimization Letters, 15, 2311–2319. Crossref, Web of Science, Google Scholar
Lv, D-Y and J-B Wang (2021b). Study on resource-dependent no-wait flow shop scheduling with different due-window assignment and learning effects. Asia-Pacific Journal of Operational Research, 38, 2150008. Link, Web of Science, Google Scholar
Mosheiov, G and D Oron (2010). Job-dependent due-window assignment based on a common flow allowance. Foundations of Computing and Decision Sciences, 35, 185–195. Google Scholar
Mosheiov, G and JB Sidney (2003). Scheduling with general job-dependent learning curves. European Journal of Operational Research, 147(3), 665–670. Crossref, Web of Science, Google Scholar
Rolim, GA and MS Nagano (2020). Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review. Computers & Industrial Engineering, 149, 106803. Crossref, Web of Science, Google Scholar
Shi, H-B and J-B Wang (2020). Research on common due window assignment flow shop scheduling with learning effect and resource allocation. Engineering Optimization, 52(4), 669–686. Crossref, Web of Science, Google Scholar
Sun, X-Y and X-N Geng (2019). Single-machine scheduling with deteriorating effects and machine maintenance. International Journal of Production Research, 57(10), 3186–3199. Crossref, Web of Science, Google Scholar
Sun, X-Y, X-N Geng and T Liu (2020). Due-window assignment scheduling in the proportionate flow shop setting. Annals of Operations Research, 292(1), 113–131. Crossref, Web of Science, Google Scholar
Wang, W (2022). Single-machine due-date assignment scheduling with generalized earliness/tardiness penalties including proportional setup times. Journal of Applied Mathematics and Computing, https://doi.org/10.1007/s12190-021-01555-4. Web of Science, Google Scholar
Wang, J-B, B Cui, P Ji and W-W Liu (2021a). Research on scheduling with position-dependent weights and past-sequence-dependent delivery times. Journal of Combinatorial Optimization, 41, 290–303. Crossref, Web of Science, Google Scholar
Wang, J-B, Y Hu and B Zhang (2021b). Common due-window assignment for single-machine scheduling with generalized earliness/tardiness penalties and a rate-modifying activity. Engineering Optimization, 53(3), 496–512. Crossref, Web of Science, Google Scholar
Wang, J-B, F Liu and J-J Wang (2019). Research on $m$ -machine flow shop scheduling with truncated learning effects. International Transactions in Operational Research, 26, 1135–1151. Crossref, Web of Science, Google Scholar
Wang, J-B, D-Y Lv, J Xu, P Ji and F Li (2021c). Bicriterion scheduling with truncated learning effects and convex controllable processing times. International Transactions in Operational Research, 28(3), 1573–1593. Crossref, Web of Science, Google Scholar
Wang, X-R, J Jin, J-B Wang and P Ji (2014). Single machine scheduling with truncated job-dependent learning effect. Optimization Letters, 8(2), 669–677. Crossref, Web of Science, Google Scholar
Wang, J-B and X-X Liang (2019). Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint. Engineering Optimization, 51(2), 231–246. Crossref, Web of Science, Google Scholar
Wang, J-B and C Wang (2011). Single-machine due-window assignment problem with learning effect and deteriorating jobs. Applied Mathematical Modelling, 35(8), 4017–4022. Crossref, Web of Science, Google Scholar
Wang, J-B and M-Z Wang (2013). Minimizing makespan in three-machine flow shops with deteriorating jobs. Computers and Operations Research, 40(2), 547–557. Crossref, Web of Science, Google Scholar
Wang, J-B and J-J Wang (2014). Single machine group scheduling with time dependent processing times and ready times. Information Sciences, 275, 226–231. Crossref, Web of Science, Google Scholar
Wang, J-B, L-Y Wang, D Wang, X-Y Wang, W-J Gao and N Yin (2009). Single machine scheduling problems with position-dependent processing times. Journal of Applied Mathematics and Computing, 30, 293–304. Crossref, Google Scholar
Wang, J-B, J Xue, B Cui and M Gao (2022). Single-machine scheduling problems with variable processing times and past-sequence-dependent delivery times. Asia-Pacific Journal of Operational Research, 39, 2150013, https://doi.org/10.1142/S0217595921500135. Link, Web of Science, Google Scholar
Wang, J-B, B Zhang, L Li, D Bai and Y-B Feng (2020). Due window assignment scheduling problems with position-dependent weights on a single machine. Engineering Optimization, 52(2), 185–193. Crossref, Web of Science, Google Scholar
Wu, Y-B, L Wan and X-Y Wang (2015). Study on due-window assignment scheduling based on common flow allowance. International Journal of Production Economics, 165, 155–157. Crossref, Web of Science, Google Scholar
Yeh, W-C and A Allahverdi (2004). A branch-and-bound algorithm for the three-machine flowshop scheduling problem with bicriteria of makespan and total flowtime. International Transactions in Operational Research, 11(3), 323–339. Crossref, Google Scholar
Yeung, WK, C Oguz and TCE Cheng (2001). Single-machine scheduling with a common due window. Computers & Operations Research, 28, 157–175. Crossref, Web of Science, Google Scholar
Yin, N (2018). Single-machine due-window assignment resource allocation scheduling with job-dependent learning effect. Journal of Applied Mathematics and Computing, 56, 715–725. Crossref, Web of Science, Google Scholar
Yin, Y, TCE Cheng, C-J Hsu and C-C Wu (2013a). Single-machine batch delivery scheduling with an assignable common due window. Omega, 41(2), 216–225. Crossref, Web of Science, Google Scholar
Yin, Y, TCE Cheng, L Wan, C-C Wu and J Liu (2015). Two-agent single-machine scheduling with deteriorating jobs. Computers and Industrial Engineering, 81, 177–185. Crossref, Web of Science, Google Scholar
Yin, Y, TCE Cheng, J Wang and C-C Wu (2013b). Single-machine common due window assignment and scheduling to minimize the total cost. Discrete Optimization, 10(1), 42–53. Crossref, Web of Science, Google Scholar
Zhu, Z, M Liu, C Chu and J Li (2019). Multitasking scheduling with multiple rate-modifying activities. International Transactions in Operational Research, 26(5), 1956–1976. Crossref, Web of Science, Google Scholar