For the most recent entries see the Petri Nets Newsletter.

Petri Net Scheduling of Parallel Manufacturing Systems Based on a New Branch and Bound Algorithm.

Jalilvand, Abolfazl; Khanmohammadi, Sohrab; Nia, Fereiddon Shabani

In: WSEAS Transaction on Circuits and Systems, Issue 5, Vol.4, pages 521-528. May 2005.

Abstract: This paper deals with the job-shop scheduling problem where n jobs must be scheduled on m parallel machines and the main objective is minimization the maximum overall completion time of all jobs called make-span. The parallel-machine scheduling problem is considered in two cases: in first case it is assumed that Jobs have no sequence-dependent setup times on machines whereas in second case it has been considered that Jobs have sequence-dependent setup times on machines. It is assumed that the jobs are available at time zero. For solving each of the scheduling problems we develop a new Branch and bound algorithm which constructs its search tree gradually and doesn't need a large size of memory. A heuristic upper-bound cost (UBC) is introduced to initialize the root node in search tree which reduces Branch and Bound computations. After Petri net modeling of the manufacturing system in each case, for applying the desired schedule on it a supervisor Petri net is introduced. The proposed methods will be verified through computational experiments.

Keywords: Manufacturing systems; Petri nets; Branch and bound; Task scheduling; Make-span.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography