A Constraint-Posting Framework for Scheduling Under Complex Constraints

C. Cheng and Stephen Smith
Proceedings Joint INRIA/IEEE Conference on Emerging Technologies and Factory Automation, October, 1995, pp. 269 - 280.


Download
  • Adobe portable document format (pdf) (172KB)
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.

Abstract
Scheduling in many practical industrial domains is complicated by the need to account for diverse and idiosyncratic constraints. Quite often these requirements are at odds with the techniques and results produced by the scheduling research community, which has focused in large part on solutions to more idealized, canonical problems. Recent research in temporal reasoning and constraint satisfaction has produced problem solving models that operate with respect to much more general representational assumptions. These frameworks offer possibilities for developing scheduling technologies that naturally extend to accommodate the peculiarities of various application domains. One critical issue, of course, is whether such generality can be obtained without sacrificing scheduling performance.

In this paper, we investigate this issue through application of a previously developed constraint satisfaction problem solving (CSP) model for deadline scheduling to a complicated, multi-product hoist scheduling problem encountered in printed circuit board (PCB) manufacturing. The goal is to maximize throughput of an automated PCB electroplating facility while ensuring feasibility with respect to process, capacity and material movement constraints. Building from a heuristic procedure generically referred to as PCP (precedence constraint posting), which relies on a temporal constraint graph representation of the problem, we straightforwardly define an extended solution procedure for minimizing makespan. In a series of comparative experiments, our procedure is found to significantly outperform previously published procedures for solving this hoist problem across a broad range of input assumptions.


Notes
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory
Number of pages: 2

Text Reference
C. Cheng and Stephen Smith, "A Constraint-Posting Framework for Scheduling Under Complex Constraints," Proceedings Joint INRIA/IEEE Conference on Emerging Technologies and Factory Automation, October, 1995, pp. 269 - 280.

BibTeX Reference
@inproceedings{Smith_1995_713,
   author = "C. Cheng and Stephen Smith",
   title = "A Constraint-Posting Framework for Scheduling Under Complex Constraints",
   booktitle = "Proceedings Joint INRIA/IEEE Conference on Emerging Technologies and Factory Automation",
   pages = "269 - 280",
   month = "October",
   year = "1995",
   volume = "1",
}