考虑部分工件不可打扰的多任务调度问题研究

展开
  • 东华大学旭日工商管理学院, 上海 201620
徐晨, E-mail: 1123315955@qq.com

收稿日期: 2020-06-11

  网络出版日期: 2021-12-11

基金资助

国家自然科学重点资助项目(71832001);国家自然科学基金(71771048)

Multitasking scheduling considering part jobs uninterrupted assignment

Expand
  • Glorious Sun School of Business and Management, Donghua University, Shanghai 201620, China

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

Abstract

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.

参考文献

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.
文章导航

/