运筹学学报 >
2021 , Vol. 25 >Issue 4: 91 - 100
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.04.008
考虑部分工件不可打扰的多任务调度问题研究
收稿日期: 2020-06-11
网络出版日期: 2021-12-11
基金资助
国家自然科学重点资助项目(71832001);国家自然科学基金(71771048)
Multitasking scheduling considering part jobs uninterrupted assignment
Received date: 2020-06-11
Online published: 2021-12-11
徐晨, 徐寅峰, 郑斐峰 . 考虑部分工件不可打扰的多任务调度问题研究[J]. 运筹学学报, 2021 , 25(4) : 91 -100 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.04.008
Multitasking scheduling can be found in various application domains, such as internet services, medical field and so on. In the original multitasking model, all jobs can be interrupted. However, some emergency jobs are not allowed to be interrupted by other jobs in the production process. Motivated by the reality, we extend the original model considering that some jobs are uninterrupted job. Our objective is to minimize the maximum completion time, the total completion time, the maximum lateness, and the weighted earliness, tardiness and common due date. We provide accurate algorithms respectively for the first three problems and an approximate algorithm for the last one. Finally, we summarize the paper and put forward suggestions for future research.
Key words: single machine; multitasking scheduling; uninterrupted; common due date
| 1 | Spink A . Multitasking information behavior and information task switching: an exploratory study[J]. Journal of Documentation, 2004, 60, 336- 345. |
| 2 | Spink A , Ozmutlu H C , Ozmutlu S . Multitasking information seeking and searching processes[J]. Journal of the American Society for Information Science Technology, 2002, 53, 639- 652. |
| 3 | Diwas Singh K C . Does multitasking improve performance? Evidence from the emergency department[J]. Social Science Electronic Publishing, 2014, 16, 168- 183. |
| 4 | Hall N G , Leung J Y T , Li C L . Multitasking via alternate and shared processing: algorithms and complexity[J]. Discrete Applied Mathematics, 2016, 208, 41- 58. |
| 5 | Sum J, Ho K. Analysis on the effect of multitasking[C]//Proceedings of the 2015 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2015: 204-209. |
| 6 | Hall N G , Leung J Y T , Li C L . The effects of multitasking on operations scheduling[J]. Production and Operations Management, 2015, 24, 1248- 1265. |
| 7 | Zhu Z , Zheng F , Chu C . Multitasking scheduling problems with a rate-modifying activity[J]. International Journal of Production Research, 2017, 55, 296- 312. |
| 8 | Zhu Z , Liu M , Chu C , et al. Multitasking scheduling with multiple rate-modifying activities[J]. International Transactions in Operational Research, 2019, 26, 1956- 1976. |
| 9 | Liu M , Wang S , Zheng F , et al. Algorithms for the joint multitasking scheduling and common due date assignment problem[J]. International Journal of Production Research, 2017, 55, 6052- 6066. |
| 10 | Ji M , Liao L , Zhang W , et al. Multitasking parallel-machine scheduling with machine-dependent slack due-window assignment[J]. International Journal of Production Research, 2019, 57, 1667- 1684. |
| 11 | Xiong X , Zhou P , Yin Y , et al. An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines[J]. Naval Research Logistics, 2019, 66, 502- 516. |
| 12 | Li S , Chen R , Tian J . Multitasking scheduling problems with two competitive agents[J]. Engineering Optimization, 2019, 52 (2): 1- 17. |
| 13 | Yang Y , Yin G , Wang C , et al. Due date assignment and two-agent scheduling under multitasking environment[J]. Journal of Combinatorial Optimization, 2020, 2, 1- 17. |
| 14 | Wang D , Yu Y , Yin Y , et al. Multi-agent scheduling problems under multitasking[J]. International Journal of Production Research, 2020, 1- 31. |
| 15 | Wang Y , Wang J , Yin Y . Due date assignment and multitasking scheduling with deterioration effect and efficiency promotion[J]. Computers & Industrial Engineering, 2020, 146, 106569. |
| 16 | Panwalkar S S , Smith M L , Seidmann A . Common due date assignment to minimize total penalty for the one machine scheduling problem[J]. Operations Research, 1982, 30, 391- 399. |
| 17 | Pinedo M. L. . Scheduling: Theory, Algorithms, and Systems[M]. New York: Springer, 2012. |
/
| 〈 |
|
〉 |