Branch and Bound-Based Scheduling of Tasks on Unrelated Parallel Multiprocessor Systems Using Petri Nets

Abstract: This paper deals with scheduling n jobs in an m-machine job-shop environment to minimizes the maximum overall completion time of all jobs called make-span. In this multiprocessor scheduling problem we assume that the jobs are available at time zero and have no sequence- dependent setup times on machines. For solving the scheduling problem we develop a new Branch and bound algorithm which constructs its search tree gradually and doesn’t need large size of memory. We will propose a lower bound cost for Branch and bound method. Furthermore for initializing the root node in the search tree a heuristic upper bound cost will be introduced which reduces the branch-and-bound computations. For applying the resultant optimum schedule on the manufacturing system a supervisor Petri net is introduced. The proposed methods will be verified through a computational experiment