单机多重任务调度极小化总完成时间问题  

Scheduling Multitasks on Single-machine to Minimize Total Completion Time

作　　者：蔡港辉 薛含钰 白丹宇 刘天一 CAI Ganghui;XUE Hanyu;BAI Danyu;LIU Tianyi(School of Maritime Economics&Management,Dalian Maritime University,Dalian 116026,China)

机构地区：[1]大连海事大学航运经济与管理学院,辽宁大连116026

出　　处：《控制工程》2023年第6期1071-1080,共10页Control Engineering of China

基　　金：国家自然科学基金面上项目(61873173)。

摘　　要：与传统机器调度不同,多重任务调度考虑人的行为因素,即主任务由于被等待任务打断而导致实际处理时间增加。研究了考虑释放时间的多重任务调度问题,首先,建立混合整数规划模型,并给出问题下界;其次,由于该问题是强NP难问题,因此针对中等规模实例,设计一种带有邻域搜索的改进粒子群优化算法,在短时间内求得问题的近似最优解;同时,针对大规模问题,提出了快速获得可行解的启发式算法,并证明了该启发式算法具备渐近最优性;最后,通过设计对比实验,验证了所提出的数学模型的正确性、改进粒子群优化算法的有效性以及启发式算法的收敛性。Different from traditional machine scheduling,multitasking scheduling considers behavioral factors that result in an increase of actual processing time due to the interruption of the primary task by the waiting task.We study the multitasking scheduling problem with release date.Firstly,we establish a mixed integer programming model and provide a lower bound for this problem.As the problem is strongly NP-hard,we design a modified particle swarm optimization algorithm with neighborhood search to obtain approximate optimal solutions quickly for medium-scale instances.Subsequently,we propose a heuristic algorithm to quickly obtain feasible solutions for large-scale problems,and prove the asymptotic optimality of the heuristic algorithm.Finally,the correctness of the proposed mathematical model,the effectiveness of the improved particle swarm optimization algorithm and the convergence of the heuristic algorithm are verified by designing comparative experiments.

关 键 词：多重任务 调度 释放时间 混合整数规划建模 粒子群优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]