Minimizing cycle time of job scheduling using Petri nets a study of heuristic methods

摘要

The objective of this paper is a study of minimizing the maximum completion time minF{sub}(max), or cycle time of the last job of a given family of jobs using flow shop heuristic scheduling techniques. The methods are Minimize Idle Time (MIT)); Campbell, Dudek and Smith, (CDS); and Palmer. An example problem with ten jobs and five machines is used to compare results of these methods. A deterministic timed colored Petri net model has been developed for scheduling problem. An execution of the deterministic timed Petri net allows to compute performance measures by applying graph traversing algorithms starting from initial global state and going into a desirable final state(s) of the production system. The objective of the job scheduling policy is minimizing the cycle time of the last job scheduled in the pipeline of a given family of jobs. Three heuristic flow shop scheduling methods have been implemented. First a suboptimal sequence of jobs to be scheduled has been generated. Secondly, a Petri net-based simulator with graphical user interface to monitor execution of the sequence on machines is dynamically designed.