Scheduling flexible flow lines with sequence-dependent setup times

Abstract

This paper examines scheduling in flexible flow lines with sequence-dependent setup times to minimize makespan. This type of manufacturing environment is found in industries such as printed circuit board and automobile manufacture. An integer program that incorporates these aspects of the problem is formulated and discussed. Because of the difficulty in solving the IP directly, several heuristics are developed, based on greedy methods, flow line methods, the Insertion Heuristic for the Traveling Salesman Problem and the Random Keys Genetic Algorithm. Problem data is generated in order to evaluate the heuristics. The characteristics are chosen to reflect those used by previous researchers. A lower bound has been created in order to evaluate the heuristics, and is itself evaluated. An application of the Random Keys Genetic Algorithm is found to be very effective for the problems examined. Conclusions are then drawn and areas for future research are identified.

Introduction

Traditional manufacturing systems have taken many general forms. In increasingly complex manufacturing environments, more complex manufacturing systems have been created in order to address such factors as limited capacity and complicated process plans. For example, the semiconductor industry uses re-entrant flow lines, in which multiple machines may exist at each stage and jobs revisit previous stages many times in a cyclic manner. The printed circuit board and automobile industries make use of flow lines with multiple machines at some stages and allow jobs to skip stages (Piramuthu et al., 1994; Agnetis et al., 1997). Moreover, these industries encounter sequence-dependent setup times which result in even more difficult scheduling problems. The scheduling objective in such industries may vary. Due date related criteria may be important. The makespan criterion has been used by many researchers and has been selected for this research. Scheduling to minimize makespan in flow lines with multiple parallel machines, jobs that may skip stages, and sequence-dependent setup times is the focus of this paper. This kind of manufacturing environment introduces new difficulties that scheduling in simple flow lines, for example, did not address.

To begin, we define the scope of the problem considered in this research. We use the term “hybrid” flow line to indicate flow lines with the presence of multiple identical machines in parallel at some or all stages, though jobs still require processing at exactly one machine per stage. A flexible flow line is a hybrid or (regular) flow line where at least one job need not be processed on any machines in at least one stage. That is, every job must be processed on at most one machine per stage. A flexible flow line consists of several stages in series. A job may not revisit a stage that it has already visited. Each stage has at least one machine, and at least one stage must have more than one machine. At this point, this structure may be considered a hybrid flow line or a flow line with multiple machines. However, the feature that makes our application a flexible flow line is that jobs may skip stages. This could occur in an industry in which some jobs do not require an operation. This situation exists in the printed circuit board manufacturing line modeled by Wittrock, 1985, Wittrock, 1988. Three of the thirteen part types required processing on only two of the three stages.

The potential variants of the basic flexible flow line described above that can be studied are nearly limitless. Now we shall describe the particular features of this research. All data in this problem are known deterministically when scheduling is undertaken. Machines are available at all times, with no breakdowns or scheduled or unscheduled maintenance. Jobs are always processed without error. Job processing cannot be interrupted (no preemption is allowed) and jobs have no associated priority values. Infinite buffers exist between stages and before the first stage and after the last stage; machines cannot be blocked because the current job has nowhere to go. There is no travel time between stages; jobs are available for processing at a stage immediately after completing processing at the previous stage. The ready time for each job is the larger of 0 and the time it completes processing on the previous stage. Machines in parallel are identical in capability and processing rate. A key characteristic of this research topic is that non-anticipatory sequence-dependent setup times exist between jobs at each stage. After completing processing of one job and before beginning processing of the next job, some sort of setup must be performed. The length of time required to do the setup depends on both the prior and the current job to be processed; that is, the setup times are sequence-dependent. Piramuthu et al. (1994) incorporate sequence-dependent setup times in their model of an actual printed circuit board line. Rios-Mercado and Bard (1998) note that sequence-dependent setup times are found in the container manufacturing industry as well as the printed circuit board industry. The formulations in Rios-Mercado and Bard (1998) indicate the assumption has been made that setup can only be performed after the machine is no longer processing any job and the job for which setup is being performed is ready. The examples in Rios-Mercado and Bard, 1999a, Rios-Mercado and Bard, 1999b discussing the container manufacturing industry state that the machines must be adjusted whenever the dimensions of the containers are changed, which presumably cannot be done until the machine is idle. We follow this concept and require the machine on which setup is to be performed to be idle and the job for which setup is required to be available as well.

This paper continues with a review of related research in Section 2. An integer programming model is presented and described in Section 3. Lower bounds are developed in Section 4 for use in evaluating schedules produced with the four heuristics described in Section 5. Using randomly generated test problems, described in Section 6, the heuristics are compared in Section 7. The quality of the lower bounds is also discussed. Section 8 concludes the paper.