Scheduling is a decision-making process that concerns the allocation of limited resources to a set of tasks with the view of optimizing one or more objectives. The primary focus of this work is the cyclic permutation flow-shop problem where a set of parts is repeatedly produced (cyclic) and the sequence of parts on all the machines remains the same (permutation). A mathematical formulation for the above problem is developed using max-plus algebra. A new concept called opportunities that identifies potential areas for improving the existing schedule is also presented. New heuristic approaches are proposed to find the optimal or sub-optimal solutions to the scheduling problem using the aforementioned mathematical formulation. The analysis of the results obtained using the developed heuristics and some of the existing heuristics on Taillard's benchmark problems have shown that the developed heuristics produce solutions of better quality and incur significantly lower computation time than the existing heuristics that were investigated.
展开▼
