作业车间调度
解算器
数学优化
计算机科学
旅行商问题
调度(生产过程)
元启发式
分解
本德分解
整数规划
分界
算法
数学
布线(电子设计自动化)
生物
计算机网络
生态学
作者
Tony Tran,Arthur Araujo,J. Christopher Beck
出处
期刊:Informs Journal on Computing
日期:2016-02-01
卷期号:28 (1): 83-95
被引量:78
标识
DOI:10.1287/ijoc.2015.0666
摘要
We study the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times and the objective of makespan minimization. Two exact decomposition-based methods are proposed based on logic-based Benders decomposition and branch and check. These approaches are hybrid models that make use of a mixed-integer programming (MIP) master problem and a specialized solver for travelling salesman subproblems. The master problem is used to assign jobs to machines, whereas the subproblems find optimal schedules on each machine given the master problem assignments. Computational results show that the decomposition models are able to find optimal solutions up to four orders of magnitude faster than the existing state of the art as well as solve problems six times larger than an existing MIP model. We further investigate the solution quality versus runtime trade-off for large problem instances for which the optimal solutions cannot be found and proved in a reasonable time. We demonstrate that the branch-and-check hybrid algorithm is able to produce better schedules in less time than the state-of-the-art metaheuristic, while also providing an optimality gap.
科研通智能强力驱动
Strongly Powered by AbleSci AI