Job-Shop Scheduling Problems Using Timed Planning

In this paper, we show how the classic job-shop scheduling problem can be modeled and solved using Timed planning processes, including both deterministic and preemptive job-shop scheduling problems. In our approach, the job shop scheduling problems can be naturally modeled as Timed Planning processes, whose complete executions correspond to feasible schedulers. The optimal scheduler, which is an execution with the minimum execution time, can be found using CLP based reasoning mechanism. Besides our approach is capable to handle the extended job-shop scheduling problems, where there are more complicated compositional operational behaviors among all jobs, which allows communications between jobs. Moreover, each job can have deadlines and relative timing constraints. We present several algorithms and heuristics for finding the optimal scheduler and test their implementation on numerous benchmark examples.

I. Introduction

Timed planning is to schedule a set of given timed tasks to fulfill certain desired properties. It has important implications in a variety of domains, e.g., real-time operating system, military planning, etc. In a broad view, Timed Planning is a generalization of the well-understood schedulability problem of a given set of timed tasks [4].