A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem

Maryam Al-Khatib (), Mohamed Haouari () and Mohamed Kharbeche ()
Additional contact information
Maryam Al-Khatib: Qatar University
Mohamed Haouari: Qatar University
Mohamed Kharbeche: Qatar University

Operational Research, 2025, vol. 25, issue 2, No 21, 21 pages

Abstract: Abstract We consider the problem of scheduling independent multi-mode tasks with multiple renewable resource constraints, aiming to minimize the weighted sum of tardinesses. This problem commonly arises in the context of multiproject scheduling. We propose three pseudo-polynomial mixed-integer programming formulations and conduct a theoretical comparative analysis of their respective linear programming relaxations. We present the results of extensive computational experiments that provide evidence that a formulation based on Dantzig–Wolfe reformulation exhibits very good empirical performance consistently solving all instances with fewer than 30 tasks. In addition, it achieved an average success rate of 94.28% for instances with tasks ranging from 40 to 100, compared to other formulations that on average achieved success rates of 64.28% and 58.57%.

Keywords: Muti-mode task scheduling; Resource constrained scheduling; Dantzig–Wolfe reformulation (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-025-00924-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:25:y:2025:i:2:d:10.1007_s12351-025-00924-2

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-025-00924-2

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().