NEW HYBRID PETRI NET, LOWEST BOUND CUT ALGORITHM FOR JOB SHOP SCHEDULING

摘要

This paper presents a new generic Petri Net based model combined with Lowest Bound Cut (LBC) algorithm for job shop scheduling problems (JSP). The objective of this algorithm is to minimize the makespan of the job shop scheduling problem. The LBC is introduced to find the lowest bound and to add the Shifting percentage (SP) to increase the lowest bound to Shifting Lower Bound (SLB). The general procedure of the new hybrid algorithm is finding the lowest solution (lowest bound) of the problem and checking the feasibility of solution. If the solution is feasible and optimal, stop searching. If the solution is unfeasible, the LBC will find the optimal solution by moving the shifting percentage forward and backward to increase and decrease Shifting lower bound and to compare with current solution from Petri Net. This paper will show that LBC can find the optimal solution. The algorithm will be illustrated example.