We study multitasking scheduling and due-window assignment problems in a single machine, which can be found in various application domains. In multitasking environment, unfinished job always interrupts in-processing job. In common due window assignment, the aim is to find optimal due window to minimise the value of the earliness and tardiness penalty. In this paper, we study two problems, where the objective of the first problem is minimise the earliness, tardiness, due-window starting time, and due-window size costs, the objective of the second problem is minmax common due-date with completion time penalty, then we obtain some analytical properties and provide polynomial time solutions. Finally, the experimental results show that the proposed methods are effective.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021079
Keywords: Multitasking scheduling, due-window, earliness-tardiness, minmax, assignment problem
@article{RO_2021__55_3_1787_0,
author = {Xu, Chen and Xu, Yinfeng and Zheng, Feifeng and Liu, Ming},
title = {Multitasking scheduling problems with a common due-window},
journal = {RAIRO. Operations Research},
pages = {1787--1798},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {3},
doi = {10.1051/ro/2021079},
mrnumber = {4275484},
zbl = {1468.90059},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021079/}
}
TY - JOUR AU - Xu, Chen AU - Xu, Yinfeng AU - Zheng, Feifeng AU - Liu, Ming TI - Multitasking scheduling problems with a common due-window JO - RAIRO. Operations Research PY - 2021 SP - 1787 EP - 1798 VL - 55 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021079/ DO - 10.1051/ro/2021079 LA - en ID - RO_2021__55_3_1787_0 ER -
%0 Journal Article %A Xu, Chen %A Xu, Yinfeng %A Zheng, Feifeng %A Liu, Ming %T Multitasking scheduling problems with a common due-window %J RAIRO. Operations Research %D 2021 %P 1787-1798 %V 55 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021079/ %R 10.1051/ro/2021079 %G en %F RO_2021__55_3_1787_0
Xu, Chen; Xu, Yinfeng; Zheng, Feifeng; Liu, Ming. Multitasking scheduling problems with a common due-window. RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1787-1798. doi: 10.1051/ro/2021079
[1] , Scheduling Algorithms. Springer, Berlin (2007). | Zbl
[2] and , Due-window assignment with identical jobs on parallel uniform machines. Eur. J. Oper. Res. 229 (2013) 41–47. | MR | Zbl | DOI
[3] , and , The effects of multitasking on operations scheduling. Prod. Oper. Manag. 24 (2015) 1248–1265. | DOI
[4] , and , Multitasking via alternate and shared processing: algorithms and complexity. Discret. Appl. Math. 208 (2016) 41–58. | MR | Zbl | DOI
[5] , , , and , Parallel machine scheduling and common due window assignment with job independent earliness and tardiness costs. Inf. Sci. 224 (2013) 109–117. | MR | Zbl | DOI
[6] , , , , and , Group scheduling with group-dependent multiple due windows assignment. Int. J. Pro. Res. 54 (2016) 1244–1256. | DOI
[7] , , , and , Multitasking Scheduling with General Aging Effect. Multiple Rate-Modifying Activities and Past-sequence-dependent Delivery Times. Working Paper (2018).
[8] , and , Multitasking Scheduling Problems with Two Competitive Agents. Eng. Optimiz. 52 (2019) 1940–1956. | MR | Zbl | DOI
[9] , and , Common due window size and location determination in a single machine scheduling problem. J. Oper. Res. Soc. 93 (1998) 68–74.
[10] , and , Single machine due-window assignment scheduling with resource-dependent processing times to minimise total resource consumption cost. Int. J. Prod. Res. 54 (2016) 1–10.
[11] , , and , Algorithms for the joint multitasking scheduling and common due date assignment problem. Int. J. Prod. Res. 55 (2017) 6052–6066. | DOI
[12] , , and , Single machine due window assignment and resource allocation scheduling problems with learning and general positional effects. J. Manuf. Syst. 43 (2017) 1–14. | DOI
[13] and , Due-window assignment with unit processing-time jobs. Nav. Res. Logist. 51 (2004) 1005–1017. | MR | Zbl | DOI
[14] and , Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ, Prentice Hall (1982). | MR | Zbl
[15] , Multitasking information behavior and information task switching: an exploratory study. J. Doc. 60 (2004) 336–345. | DOI
[16] , and , Multitasking information seeking and searching processes. J. Am. Soc. Inform. Sci. Tech. 53 (2014) 639–652. | DOI
[17] , , and , Multi-agent scheduling problems under multitasking. Int. J. Prod. Res. 59 (2020) 1–31.
[18] , and , Due date assignment and multitasking scheduling with deterioration effect and efficiency promotion. Comput. Ind. Eng. 146 (2020) 106569. | DOI
[19] , , , and , An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines. Nav. Res. Logist. 66 (2019) 502–516. | MR | Zbl | DOI
[20] , and , Scheduling problems with multiple due windows assignment and controllable processing times on a single machine. Int. J. Prod. Econ. 150 (2014) 96–103. | DOI
[21] , , and , Due date assignment and two-agent scheduling under multitasking environment. J. Comb. Optim. 2 (2020). | MR | Zbl
[22] , , and , single-machine batch delivery scheduling with an assignable common due window. Omega 41 (2013) 216–225. | DOI
[23] , and , , Single-machine batch delivery scheduling with an assignable common due date and controllable processing times. Comp. Ind. Eng. 65 (2013) 652–662. | DOI
[24] , , , Multitasking scheduling problems with a rate-modifying activity. Int. J. Prod. Res. (2016) 1–17.
[25] , , and , Multitasking scheduling with multiple rate-modifying activities. Int. Trans. Oper. Res. (2017) 1–21. | MR | Zbl
Cité par Sources :
