期刊
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
卷 -, 期 -, 页码 -出版社
WILEY
DOI: 10.1111/itor.13240
关键词
coupled task scheduling; mixed-integer program; makespan minimization; binary search; relax-and-solve matheuristic; relax-and-solve
资金
- UTS International Research Scholarship (IRS)
- UTS President's Scholarship (UTSP)
- Australian Research Council Discovery Early Career Researcher Award - Australian Government [DE170100234]
- Council of Australian University Librarians
- Australian Research Council [DE170100234] Funding Source: Australian Research Council
This article proposes a new method for the general single machine coupled task scheduling problem and demonstrates its superiority in improving solution quality and reducing the average gap to the best known solution.
The general single machine coupled task scheduling problem with the objective function of minimizing the makespan, which is strongly NP-hard, aims to schedule a set of coupled task jobs on one machine such that the completion time of the last job is minimized. We propose a new mixed-integer program (MIP) for the problem. We also propose a relax-and-solve (R&S) matheuristic algorithm as the solution method. We show that the new MIP outperforms the available models and improves the quality of solutions. Also, the proposed MIP significantly improves the average gap to the best known feasible solution of an existing binary search algorithm. We show that our R&S matheuristic produces new best solutions for almost 50% of the instances.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据