工业工程

工业工程 ›› 2022, Vol. 25 ›› Issue (1): 114-122.doi: 10.3969/j.issn.1007-7375.2022.01.014

• 实践与应用 • 上一篇    下一篇

考虑任务拆分特性与簇准备时间的并行机调度

朱松平, 王小明, 鄢敏杰, 陈庆新, 毛宁   

  1. 广东工业大学 广东省计算机集成制造重点实验室, 广东 广州 510006
  • 收稿日期:2020-03-13 发布日期:2022-03-02
  • 通讯作者: 王小明(1986—)，男，江西省人，副教授，博士，主要研究方向为随机项目调度与监控、制造与服务系统随机建模优化等。 E-mail: simonwang@gdut.edu.cn E-mail:simonwang@gdut.edu.cn
  • 作者简介:朱松平(1996—)，男，江西省人，硕士研究生，主要研究方向为项目调度与机器调度
  • 基金资助:
    国家自然科学基金资助项目(71972053; 61973089; 51505090; 51775120)

Parallel Machines Scheduling with Job-splitting Property and Family Setups

ZHU Songping, WANG Xiaoming, YAN Minjie, CHEN Qingxin, MAO Ning   

  1. Provincial Key Laboratory of Computer Integrated Manufacturing, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2020-03-13 Published:2022-03-02

RichHTML

57

PDF

4972

摘要： 在印制电路板钻孔任务调度等工程实际中，普遍存在一类具有任务拆分特性与簇准备时间的并行机调度问题，尚缺乏高效的优化模型和方法。针对该问题，首先建立以总拖期最小为目标的数学模型，以约束的形式将两个现有优势定理嵌入其中。为了高效求解实际规模问题，进一步提出嵌入优势定理的模拟退火算法。最后，基于随机生成的算例构造计算实验，以验证所建模型和算法的有效性。实验结果表明，嵌入优势定理的数学模型在问题求解规模和计算效率方面均优于现有数学模型，嵌入优势定理的模拟退火算法同样优于现有模拟退火算法。

关键词: 并行机调度, 任务拆分, 簇准备时间, 优势定理, 整数规划, 模拟退火算法

Abstract: The parallel machines scheduling problem with job-splitting property and family setups is common in engineering practice such as drilling task scheduling of printed circuit boards. Until now, there is still a lack of efficient optimization model and method. To address this issue, a mathematical model with the objective to minimize the total tardiness is first constructed, and then two existing dominance rules are embedded in the form of constraints. In order to solve a practical size problem efficiently, the simulated annealing algorithms with embedded dominance rules are proposed. Finally, computational experiments based on randomly generated instances are designed to validate the effectiveness of the constructed models and algorithms. Experimental results show that the proposed mathematical model with embedded dominance rules is superior to the existing model in terms of the size of the problem that can be solved and the computational efficiency. In addition, the proposed simulated annealing algorithm with embedded dominance rules are also superior to the existing simulated annealing algorithm.

Key words: parallel machines scheduling, job splitting, family setups, dominance rules, integer programming, simulated annealing algorithm

中图分类号: