Complete MCS-Based Search: Application to Resource Constrained Project Scheduling
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 181-185.
Abstract
This paper describes a simple complete search for cumulative scheduling based on the detection and resolution of minimal critical sets (MCS). The heuristic for selecting MCSs relies on an estimation of the related reduction of the search space. An extension of the search procedure using selfadapting shaving is proposed. The approach was implemented on top of classical constraint propagation algorithms and tested on resource constrained project scheduling problems (RCPSP). We were able to close more than 15% of the previously open problems of the PSPLIB [Kolisch and Sprecher, 1996] and improve more than 31% of the best known lower bounds on those heavily studied problems. Other new results on open-shop and cumulative job-shop scheduling are reported.
@inproceedings{ijcai2005p45,
title = {Complete MCS-Based Search: Application to Resource Constrained Project Scheduling},
author = {Laborie, Philippe},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {181--185},
year = {2005},
url = {https://ijcai.org/proceedings/2005/45},
}
TY - CPAPER TI - Complete MCS-Based Search: Application to Resource Constrained Project Scheduling AU - Laborie, Philippe T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 181 EP - 185 UR - https://ijcai.org/proceedings/2005/45 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
