Scheduling FMS with due dates based on Petri net state equations

This paper presents a heuristic search approach for scheduling flexible manufacturing systems (FMS) with due dates based on the Petri net state equation. It is known that the state equation of a Petri net has a solution if the goal marking can be reached from the initial marking. In terms of scheduling, this denotes that the costs of jobs can be obtained from the solution. In this paper, the idea of jobwise Petri nets is introduced. A jobwise net is a part of the model of an FMS. It is only associated with one job and the resources that the job uses. A model of N jobs can be split into N jobwise net models. We combine jobwise Petri nets and the state equations to implement the search algorithm. The objective is to minimize weighted tardiness (lateness), which is the difference of the completion time of a job and its due date. In order to show that this scheduling method can get near-optimal solutions, we compare it with some commonly used dispatching rules by simulations