A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem
<p dir="ltr">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...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| منشور في: |
2025
|
| الموضوعات: | |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513534154506240 |
|---|---|
| author | Maryam Al-Khatib (19561909) |
| author2 | Mohamed Haouari (10340697) Mohamed Kharbeche (6579296) |
| author2_role | author author |
| author_facet | Maryam Al-Khatib (19561909) Mohamed Haouari (10340697) Mohamed Kharbeche (6579296) |
| author_role | author |
| dc.creator.none.fl_str_mv | Maryam Al-Khatib (19561909) Mohamed Haouari (10340697) Mohamed Kharbeche (6579296) |
| dc.date.none.fl_str_mv | 2025-05-05T03:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1007/s12351-025-00924-2 |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/A_comparative_analysis_of_MIP_formulations_for_the_multi-mode_resource-constrained_independent_task_scheduling_problem/30406234 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Engineering Manufacturing engineering Information and computing sciences Computer vision and multimedia computation Distributed computing and systems software Muti-mode task scheduling Resource constrained scheduling Dantzig–Wolfe reformulation |
| dc.title.none.fl_str_mv | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p dir="ltr">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%.</p><h2>Other Information</h2><p dir="ltr">Published in: Operational Research<br>License: <a href="https://creativecommons.org/licenses/by/4.0" target="_blank">https://creativecommons.org/licenses/by/4.0</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1007/s12351-025-00924-2" target="_blank">https://dx.doi.org/10.1007/s12351-025-00924-2</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_df14cd8965ffa73cff5b28a7243754cd |
| identifier_str_mv | 10.1007/s12351-025-00924-2 |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/30406234 |
| publishDate | 2025 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problemMaryam Al-Khatib (19561909)Mohamed Haouari (10340697)Mohamed Kharbeche (6579296)EngineeringManufacturing engineeringInformation and computing sciencesComputer vision and multimedia computationDistributed computing and systems softwareMuti-mode task schedulingResource constrained schedulingDantzig–Wolfe reformulation<p dir="ltr">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%.</p><h2>Other Information</h2><p dir="ltr">Published in: Operational Research<br>License: <a href="https://creativecommons.org/licenses/by/4.0" target="_blank">https://creativecommons.org/licenses/by/4.0</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1007/s12351-025-00924-2" target="_blank">https://dx.doi.org/10.1007/s12351-025-00924-2</a></p>2025-05-05T03:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1007/s12351-025-00924-2https://figshare.com/articles/journal_contribution/A_comparative_analysis_of_MIP_formulations_for_the_multi-mode_resource-constrained_independent_task_scheduling_problem/30406234CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/304062342025-05-05T03:00:00Z |
| spellingShingle | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem Maryam Al-Khatib (19561909) Engineering Manufacturing engineering Information and computing sciences Computer vision and multimedia computation Distributed computing and systems software Muti-mode task scheduling Resource constrained scheduling Dantzig–Wolfe reformulation |
| status_str | publishedVersion |
| title | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem |
| title_full | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem |
| title_fullStr | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem |
| title_full_unstemmed | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem |
| title_short | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem |
| title_sort | A comparative analysis of MIP formulations for the multi-mode resource-constrained independent task scheduling problem |
| topic | Engineering Manufacturing engineering Information and computing sciences Computer vision and multimedia computation Distributed computing and systems software Muti-mode task scheduling Resource constrained scheduling Dantzig–Wolfe reformulation |