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

doi:10.15960/j.cnki.issn.1007-6093.2021.04.008

运筹学学报 ›› 2021, Vol. 25 ›› Issue (4): 91-100.doi: 10.15960/j.cnki.issn.1007-6093.2021.04.008

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

徐晨(), 徐寅峰, 郑斐峰

东华大学旭日工商管理学院, 上海 201620

收稿日期:2020-06-11 出版日期:2021-12-15 发布日期:2021-12-11
通讯作者: 徐晨 E-mail:1123315955@qq.com
作者简介:徐晨, E-mail: 1123315955@qq.com
基金资助:
国家自然科学重点资助项目(71832001);国家自然科学基金(71771048)

Multitasking scheduling considering part jobs uninterrupted assignment

Chen XU(), Yinfeng XU, Feifeng ZHENG

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

Received:2020-06-11 Online:2021-12-15 Published:2021-12-11
Contact: Chen XU E-mail:1123315955@qq.com

摘要/Abstract

摘要：

多任务调度问题存在于各种应用领域，如因特网服务领域，医疗领域等。经典的多任务调度模型中所有工件均可被其他等待工件打扰，且仅打扰一次。然而在生产实践过程中，有些紧急工件是不允许被其他工件打扰。在此启发下，对原有模型进行扩展，研究了在单机多任务环境下部分工件不可打扰的调度问题，模型目标包括最小化最大完工时间，最小化总完工时间，最小化最大延迟以及最小化加权提前期、拖延期和共同交货期之和。对于前三个目标给出了精确算法，对于最后一个目标给出了启发式算法。最后，对今后的研究提出了建议。

关键词: 单机, 多任务调度, 不可打扰, 共同交货期

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.

Key words: single machine, multitasking scheduling, uninterrupted, common due date

中图分类号:

O224

徐晨, 徐寅峰, 郑斐峰. 考虑部分工件不可打扰的多任务调度问题研究[J]. 运筹学学报, 2021, 25(4): 91-100.

Chen XU, Yinfeng XU, Feifeng ZHENG. Multitasking scheduling considering part jobs uninterrupted assignment[J]. Operations Research Transactions, 2021, 25(4): 91-100.

图/表 1

参考文献 17

1	Spink A . Multitasking information behavior and information task switching: an exploratory study[J]. Journal of Documentation, 2004, 60, 336- 345. doi: 10.1108/00220410410548126
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. doi: 10.1002/asi.10124
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. doi: 10.1016/j.dam.2016.03.018
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. doi: 10.1111/poms.12331
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. doi: 10.1080/00207543.2016.1208852
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. doi: 10.1111/itor.12393
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. doi: 10.1080/00207543.2017.1321804
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. doi: 10.1080/00207543.2018.1497312
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. doi: 10.1002/nav.21863
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. doi: 10.1007/s10878-020-00600-5
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. doi: 10.1287/opre.30.2.391
17	Pinedo M. L. . Scheduling: Theory, Algorithms, and Systems[M]. New York: Springer, 2012.

编辑推荐 0

Metrics

阅读次数

全文

540

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	358	0	0	182

来源	本网站	其他网站

次数	282	258
比例	52%	48%

摘要

2875

最新录用	在线预览	正式出版

0	0	2875

来源	本网站	其他网站

次数	1696	1179
比例	59%	41%

[1]	张新功. 基于加工时间之和学习效应下的单机成组排序问题[J]. 运筹学学报, 2013, 17(1): 98-105.
[2]	王成飞, 张玉忠, 苗翠霞. 两类加工时间是一般函数的单机排序问题[J]. 运筹学学报, 2011, 15(2): 59-67.

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

Multitasking scheduling considering part jobs uninterrupted assignment

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 17

相关文章 2

编辑推荐 0

Metrics

本文评价