Exploiting process plan flexibility in production scheduling: A multi-objective approach

When solving a product/process design problem, we must exploit the available degrees of freedom to cope with a variety of issues. Alternative process plans can be generated for a given product, and choosing one of them has implications on manufacturing functions downstream, including planning/scheduling Flexible process plans can be exploited in real time to react to machine failures, but they are also relevant for off-line scheduling. On the one hand, we should select a process plan in order to avoid creating bottleneck machines, which would deteriorate the schedule quality; on the other one we should aim at minimizing costs. Assessing the tradeoff between these possibly conflicting objectives is difficult; actually, it is a multi-objective problem, for which available scheduling packages offer little support. Since coping with a multi-objective scheduling problem with flexible process plans by an exact optimization algorithm is out of the question, we propose a hierarchical approach, based on a decomposition into a machine loading and a scheduling sub-problem. The aim of machine loading is to generate a set of efficient (non-dominated) solutions with respect to the load balancing and cost objectives, leaving to the user the task of selecting a compromise solution. Solving the machine loading sub-problem essentially amounts to selecting a process plan for each job and to routing jobs to the machines; then a schedule must be determined. In this paper we deal only with the machine loading subproblem, as many scheduling methods are already available for the problem with fixed process plans. The machine loading problem is formulated as a bicriterion integer programming model, and two different heuristics are proposed, one based on surrogate duality theory and one based on a genetic descent algorithm. The heuristics are tested on a set of benchmark problems. (C) 1999 Elsevier Science B.V. All rights reserved.