Graphics enhanced version of this site

Scheduling by iterative partition of bottleneck conflicts
N. Muscettola
Proceedings of the Ninth Conference on Artificial Intelligence for Applications, March, 1993, pp. 49 - 55.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [687 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

The author describes conflict partition scheduling (CPS), a novel methodology that constructs solutions to scheduling problems by repeatedly identifying bottleneck conflicts and posting constraints to resolve them. The identification of bottleneck conflicts is based on a capacity analysis using a stochastic simulation methodology. Once a conflict is identified, CPS does not attempt to resolve it completely; instead it introduces constraints that merely decrease its criticality. By reducing the amount by which each scheduling decision prunes the search space, CPS tries to minimize the chance of getting lost in blind alleys. The effectiveness of CPS was demonstrated by an experimental analysis that compared CPS to two current scheduling methods: micro-opportunistic constraint-directed search and min-conflict iterative repair. CPS is shown to perform better than both on a standard benchmark of constraint satisfaction scheduling problems

Associated center: CIMDS
Associated lab/group: Intelligent Coordination and Logistics Laboratory

N. Muscettola, "Scheduling by iterative partition of bottleneck conflicts," Proceedings of the Ninth Conference on Artificial Intelligence for Applications, March, 1993, pp. 49 - 55.

@inproceedings{Muscettola_1993_5647,
   author = "Nicola Muscettola",
   title = "Scheduling by iterative partition of bottleneck conflicts",
   booktitle = "Proceedings of the Ninth Conference on Artificial Intelligence for Applications",
   month = "March",
   year = "1993",
   pages = "49 - 55"
}