On-line Planning and Scheduling for High-speed Manufacturing

All Papers

We describe a real manufacturing problem that lies between job shop scheduling and temporal planning. The setting is on-line in the sense that new jobs arrive asynchronously, perhaps several per second, while plans for previous jobs are being executed. We formalize the problem as a variant of STRIPS extended with action durations and resources. We present a hybrid algorithm for this problem that combines techniques from partial-order scheduling and state-space planning. No domain-specific search control is used. Our current implementation successfully controls two prototype plants and our technology is anticipated to enable a new line of products. By integrating planning and scheduling, we enable high productivity even for complex plants.