The Local Search Approach to Flexible Flow Line Scheduling

Local search methods are presented for scheduling a flexible flow line. We consider the problem of entry point sequencing, that is, deciding the order in which to present the jobs to the system. Results 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. The 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 they are capable of producing entry point sequences that are, for all practical purposes, close to optimal. We then proceed to describe a new method for choosing starting sequences for local search methods which is based on the use of sphere partitions and present some initial results.