The Robotics Institute

Carnegie Mellon Robotics Institute

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

One challenge for research in constraint-based scheduling has been to produce scalable solution procedures under fairly general representational assumptions. Quite often, the computational burden of techniques for reasoning about more complex types of temporal and resource capacity constraints places fairly restrictive limits on the size of problems that can be effectively addressed. In this paper, we focus on developing a scalable heuristic procedure to an extended, multi-capacity resource version of the job shop scheduling problem (MCJSSP). Our starting point is a previously developed procedure for generating feasible solutions to more complex, multi-capacity scheduling problems with maximum time lags. Adapting this procedure to exploit the simpler temporal structure of MCJSSP, we are able to produce a quite efficient solution generator. However, the procedure only indirectly attends to MCJSSP's objective criterion and produces sub-optimal solutions. To provide a scalable, optimizing procedure, we propose a simple, local-search procedure called {\em iterative flattening}, which utilizes the core solution generator to perform an extended iterative improvement search. Despite its simplicity, experimental analysis shows the iterative improvement search to be quite effective. On a set of reference problems ranging in size from 100 to 900 activities, the iterative flattening procedure efficiently and consistently produces solutions within 10% of computed upper bounds. Overall, the concept of iterative flattening is quite general and provides an interesting new basis for designing more sophisticated local search procedures.

Notes

Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems

Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory

Text Reference

A. Cesta, A. Oddi, and Stephen Smith , "Iterative Flattening: A Scalable Method for Solving Multi-Capacity Scheduling Problems," Proceedings National Conference on Artificial Intelligence (AAAI-00), July, 2000.

BibTeX Reference

@inproceedings{Smith__2000_3754,
   author = "A. Cesta and A. Oddi and Stephen {Smith }",
   title = "Iterative Flattening: A Scalable Method for Solving Multi-Capacity Scheduling Problems",
   booktitle = "Proceedings National Conference on Artificial Intelligence (AAAI-00)",
   month = "July",
   year = "2000",
}

The Robotics Institute

Menu