زمان بندی تولید کارگاهی وابسته به توالی چندمعیاری با استفاده از الگوریتم ژنتیک

Real world job shops have to contend with jobs due on different days, material ready times that vary, reentrant workflows and sequence-dependent setup times. The problem is even more complex because businesses often judge solution goodness according to multiple competing criteria. Producing an optimal solution would be time consuming to the point of rendering the result meaningless. Commonly used heuristics such as shortest processing time (SPT) and earliest due date (EDD) can be used to calculate a feasible schedule quickly, but usually do not produce schedules that are close to optimal in these job shop environments. We demonstrate that genetic algorithms (GA) can be used to produce solutions in times comparable to common heuristics but closer to optimal. Changing criteria or their relative weights does not affect the running time, nor does it require programming changes. Therefore, a GA can be easily applied and modified for a variety of production optimization criteria in a job shop environment that includes sequence-dependent setup times.

Sequence-dependent setup times in job shops are very common. Moving from one family of parts to another can involve a significant setup time compared to producing similar parts to those that were just run. This type of problem is mathematically complex to solve optimally, therefore simplistic heuristics like shortest processing time (SPT), earliest due date (EDD), first-in-first-out (FIFO) or even ad hoc scheduling are often used because management can readily understand them. Additional complexity arises because management routinely wants to consider multiple criteria when evaluating schedule goodness. In many manufacturing environments, the sequence of jobs run on a particular machine affects the setup times. The author had the opportunity to work at a sheet metal fabricator in 1991 where the job shop environment had machines where the setup times would vary according to the sequence of jobs processed. For example, the turret punch could use the same punch for jobs of similar products while a different product would require the punch to be changed on the machine. The plant simply batched together alike jobs until customers called and complained about their orders being late, then the order of jobs queued in front of the machines was altered to reflect which customer had called most recently. The setup times for each order are different due to different previous job order. The similar job grouping by type was used in front of the numerical controlled (NC) machine. This situation is common in many environments with flexible manufacturing, where setting up once to run a particular major class of parts is done, then minor setups to alter specific products are done within the same major part class. The setup time for a particular major class of parts typically depends upon the previous part family.We consider a job shop environment with multiple machines where multiple jobs consisting of a set number of operations each must be scheduled according to various criteria. We will demonstrate that a simple genetic algorithm (GA) can produce a good result quickly for managers for a complex set of sequence-dependent job shop scheduling problems. A GA is a viable approach to solving optimization problems. The principles of a GA proposed by Holland (1975) are the foundation of all GAs. A GA simulates evolution via natural selection on a model of a problem. The idea is to evolve a population of candidate solutions to a given problem using operators inspired by natural genetic variation and natural selection (Mitchell, 1996). The basic structure of a GA is: • Create an initial set of solutions. • Score the initial set of solutions. • Loop for reproduction. – Copy the best solution to a new population. – Randomly Mutate a small subset of the population to introduce solution variety. – Mating to combine solutions in the population according to their fitness, in terms of score goodness, to create new solutions. – Score the new set of solutions. • Until termination criteria. This paper is organized into the following sections; Section 2 is a literature review of job shop scheduling, sequence-dependent setups in scheduling, and GAs as an optimization tool. Section 3 is a description of the problem we are trying to solve. Section 4 is the mechanism behind how GAs work in general and specifics on our GA. Section 5 explains how the tests are set up. Section 6 is a robustness test of the GA for various types of job shop problems. Section 7 is the summary and discussion of the implications of the results.

Job shop scheduling with sequence-dependent setup times is common in many industries. The sheet metal fabricator mentioned in the introduction is one example. Environments where processing a light color product after a dark color one results in significantly more machine cleaning to avoid bleed through is a situation where the production planner will want to minimize idle time by scheduling light to dark where possible. The apparel assembly industry routinely encounters sequence-dependent setup times when assigning operators to machines. A customized version of this algorithm was demonstrated for the CEO of a custom built, high-end race car assembler. Sequencing of jobs to minimize downtime due to switching thicknesses of carbon fiber materials when applying composite layers to the car frame is estimated to decrease their average cycle time by 18%. Common heuristics and GAs can find quick, feasible solutions to job shop scheduling problems that involve complexities such as sequence-dependent setup times, spaced release dates and multiple criteria. Common heuristics run quickly but do not converge to optimal like a GA. Because of the speed with which the GA runs, changes to customer release and due dates, routing changes, and order deletions and additions can be reflected in a new schedule quickly. The results for this study demonstrate that near optimal solutions can be achieved in a very short timeframe with the GA. The longer the GA is allowed to run, the more likely the final solution will be better according to the planner’s criteria. The common heuristics used here achieved a wide variety of results which are highly dependent on the problem being solved. Since all 18 heuristics can be run together in several seconds, a planner could run the GA and these heuristics and take the best result. This would give a solution with a lower bound of the best heuristic, but with the ability to be much closer to optimal depending on how long the GA is allowed to run. We have shown that this GA performance is relatively insensitive to the problem data and criteria for evaluation. This GA can be easily enhanced by adding resource calendars, alternate machines with different costs or scrap rates, learning curves on machines and other complexities.