Heuristic Methods for Flexible Flow Line Scheduling

Heuristic methods are presented for scheduling a flexible flow line. Two problems are considered: entry point sequencing, that is, deciding the order in which to present the jobs to the system, and dispatching, that is, deciding at each machine which job to start next. The results of these methods on test and realistic problems are described. The strength of the approach lies in its ability to take into account various line phenomena, such as setups, finite buffers, blocking and starvation, machine breakdowns and downtimes, the current and subsequent states (at rescheduling intervals) of the line. It is also easy to incorporate heuristics available from previous experience with similar lines. Various optimization techniques are investigated including myopic and local search methods. The most successful technique developed uses local perturbation to successively obtain improved schedules. In test cases where the optimal schedule is obtainable, we are able to produce solutions within a few percent of the optimal. Our experience with these methods is sufficiently encouraging to lead us to conjecture that these methods are capable of producing entry point sequences that are, for all practical purposes, close to optimal. Various methods of dispatching are considered which try to minimize the effects of setup times and blocking. While dispatching is found to be useful in setup-intensive lines, one of our conclusions is that care must be taken as plausibly helpful rules can lead to unexpected deterioration of performance.