Accession Number : ADA255839
Title : Scheduling by Iterative Partition of Bottleneck Conflicts
Descriptive Note : Technical rept.
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST
Personal Author(s) : Muscettola, Nicola
Report Date : Feb 1992
Pagination or Media Count : 17
Abstract : In this paper we describe 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. Moreover, the capacity analysis metrics computed at each decision step give an indication of the areas of the search space where pruning is more likely to be effective. CPS effectiveness is demonstrated by the results of an extensive experimental analysis that compares it to two current scheduling methods: micro-opportunistic constraint-directed search and min-conflict iterative repair. CPS is shown to significantly outperform both of them on a standard benchmark of constraint satisfaction scheduling problems.
Descriptors : *SCHEDULING , *ITERATIONS , SIMULATION , METHODOLOGY , CONFLICT , IDENTIFICATION , REPAIR
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE