In: 9th WSEAS International Multi-Conference on Circuites, Systems, Communcations and Computers, CSCC-2005, pages 1-6. July 2005. (Proceedings is in CD).
Abstract: This paper deals with scheduling jobs in an machine job-shop environment to minimize 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.
Keywords: Manufacturing systems; Petri nets; Branch and Bound; Task scheduling; Make-span.