The coupled task scheduling problem: an improved mathematical program and a new solution algorithm

doi:10.1111/itor.13240

The coupled task scheduling problem: an improved mathematical program and a new solution algorithm

2022-12-13

0

OA

AI

DOI：10.1111/itor.13240

原文链接

原文求助

摘要

En 中文

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.

Keyword:

coupled task scheduling

mixed-integer program

makespan minimization

binary search

relax-and-solve matheuristic

relax-and-solve

The coupled task scheduling problem: an improved mathematical program and a new solution algorithm

摘要

期刊

机构