|本期目录/Table of Contents|

[1]胡觉亮,李志林,董建明.工件加工需要额外资源的平行机调度问题[J].浙江理工大学学报,2022,47-48(自科五):791-797.
　HU Jueliang,LI Zhilin,DONG Jianming.The parallel machine scheduling problem for job  processing requiring extra resources[J].Journal of Zhejiang Sci-Tech University,2022,47-48(自科五):791-797.
点击复制

工件加工需要额外资源的平行机调度问题()
分享到：

浙江理工大学学报[ISSN:1673-3851/CN:33-1338/TS]

卷:
第47-48卷
期数:
2022年自科第五期
页码:
791-797
栏目:
出版日期:
2022-09-10

文章信息/Info

Title:
The parallel machine scheduling problem for job  processing requiring extra resources
文章编号:
1673-3851 (2022) 09-0791-07
作者:
胡觉亮; 李志林; 董建明
浙江理工大学理学院，杭州 310018
Author(s):
HU Jueliang; LI Zhilin; DONG Jianming
School of Science, Zhejiang Sci-Tech University, Hangzhou 310018, China
关键词:
额外资源; 平行机; 调度问题; 整数规划; 近似算法
分类号:
O223
文献标志码:
A
摘要:
针对工件加工需要额外资源且额外资源有两个单位可用的平行机调度问题，目标是极小化最大完工时间，给出了一个近似算法。首先，说明了该问题是NP-难的，并给出了该问题的整数规划模型和最优解的下界；然后，设计了该问题的一个近似算法，通过分析算法的性质，证明了该算法的最坏情况界不大于3-2/m；最后，通过大量的数值实验验证算法在平均情况下的性能。数值实验结果表明，该算法在工件数、额外资源数和机器数等因素扰动下都体现了较好的性能。该算法可为需要额外资源调度问题的高效算法设计提供参考。

参考文献/References:

［1］胡觉亮, 杨佳雯, 苏晓彤, 等. 机器带周期性维护时段的加工与运输协同排序问题［J］. 浙江理工大学学报(自然科学版), 2016, 35(6): 951-956.

［2］王霄汉, 张霖, 任磊, 等. 基于强化学习的车间调度问题研究简述［J］. 系统仿真学报, 2021, 33(12): 2782-2791.

［3］薛玲玲. 作业车间调度的块结构邻域搜索遗传算法［J］.计算机集成制造系统, 2021, 27（10）：2848-2857.

［4］Kellerer H, Strusevich V A. Scheduling parallel dedicated machines under a single nonshared resource［J］. European Journal of Operational Research, 2003, 147(2): 345-364.

［5］Li Y Z, Wang F, Lim A. Resource constraints machine scheduling: A genetic algorithm approach［C］//The 2003 Congress on Evolutionary Computation. Canberra, ACT, Australia: IEEE, 2003: 1080-1085.

［6］Kellerer H, Strusevich V A. Scheduling problems for parallel dedicated machines under multiple resource constraints［J］. Discrete Applied Mathematics, 2003, 133(1/2/3): 45-68.

［7］Hebrard E, Huguet M J, Jozefowiez N, et al. Approximation of the parallel machine scheduling problem with additional unit resources［J］. Discrete Applied Mathematics, 2016, 215: 126-135.

［8］Godet A, Lorca X, Hebrard E, et al. Using approximation within constraint programming to solve the parallel machine scheduling problem with additional unit resources［C］//ThirtyFourth AAAI Conference on Artificial Intelligence (AAAI 20). New York: Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34(2): 1512-1519.

［9］Strusevich V A. Approximation algorithms for makespan minimization on identical parallel machines under resource constraints［J］. Journal of the Operational Research Society, 2021, 72(9): 2135-2146.

［10］Janssen T, Swennenhuis C, Bitar A, et al. Parallel machine scheduling with a single resource per job. (2018-11-16)［2022-05-14］.

undefined

备注/Memo

备注/Memo:
收稿日期： 2022-05-14
网络出版日期：2022-06-25
基金项目： 国家自然科学基金项目（11971435）
作者简介： 胡觉亮（1958-），男，浙江杭州人，教授，主要从事运筹学与组合优化、近似算法设计及应用方面的研究
通信作者： 董建明，E-mail：djm226@163.com
更新日期/Last Update: 2022-09-07