EUVIMEDDescoperă EUVIMED
Open access · CC BY-NC-ND 4.0

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

Mostafa Khatami, Amir Salehipour

International Transactions in Operational Research · 2024-07 · 31 (4) · 2399-2426

DOI: 10.1111/itor.13240 ↗

At a glance

Journal article in International Transactions in Operational Research, published online on 2022-12-13. Written by Mostafa Khatami and 1 co-authors. Cited 2 times so far (Crossref); 30 references. The full text is freely available (open access, CC BY-NC-ND 4.0). Funded by: Australian Government, Australian Research Council.

RezumatDate bibliograficeCiteRelated studies

Abstract (original language)

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.

Funding

  • Australian Government
  • Australian Research Council

Cite

APA

Khatami, M., & Salehipour, A. (2024). The coupled task scheduling problem: an improved mathematical program and a new solution algorithm. International Transactions in Operational Research, 31(4), 2399-2426. https://doi.org/10.1111/itor.13240

Vancouver

Khatami M, Salehipour A. The coupled task scheduling problem: an improved mathematical program and a new solution algorithm. International Transactions in Operational Research. 2024;31(4):2399-2426. doi:10.1111/itor.13240

BibTeX
@article{Khatami2024,
  author = {Khatami, Mostafa and Salehipour, Amir},
  title = {The coupled task scheduling problem: an improved mathematical program and a new solution algorithm},
  journal = {International Transactions in Operational Research},
  year = {2024},
  volume = {31},
  number = {4},
  pages = {2399--2426},
  doi = {10.1111/itor.13240}
}
Start for free →