From: Ray Vickson Newsgroups: comp.programming,sci.math Subject: Re: Problem: optimal processing order Date: Thu, 29 Oct 1998 18:22:03 -0500 jbradley4149@my-dejanews.com wrote: > > Hi all! > > I've got an interesting problem for you. > > We've got a factory in which we manufacture custom products, according to > customer specifications. We want to produce a maximum amount of products. > > The main bottleneck is a two-machine installation, as illustrated below > > production -----> machine 1 ---queue---> machine 2 -----> post > line processing > > The production line is capable of producing more products than machine 1 > can process, so that's not the problem. > > All (custom) products have different processing times for machines 1 and > 2, and these times are known in advance. For example (processing time in > minutes): > machine > 1 2 > ---------- > product 1: 2 4 > 2 3 1 > 3 5 2 > 4 1 5 > 5 2 5 > 6 3 2 > > The products must be processed by machine 1 first, and then by machine 2. > If machine 2 is still busy when products arrive from machine 1, the > products are placed in a queue (that can hold 'infinitely many' products). > > If we process the products of the above table in that order, we get the > scheme ('2--' means 'processing product 2'): > > 111111111122222 > time 123456789012345678901234 > ------------------------ > machine 1: 1-2--3----45-6-- > 2 1---2 3-4----5----6- > > The total processing time for these 6 products, ordered in this way, is > 24. But we can order them differently, to reduce the total processing > time, for example: > > 11111111112 > time 12345678901234567890 > -------------------- > machine 1: 41-3----5-6--2-- > 2 4----1---3-5----6-2 > > The total processing time now is only 20. > > The problem is to determine the optimal product order, that minimizes the > total processing time. > > I can just check all possible orders, but that's extremely slow with many > products. I've thought of many other possibilities, but they don't work > out - no one guarantees optimal ordering. > > So my question is: is there a fast way to do this? If yes, what way; if > no, why not? Hints are also welcome. The solution to your problem has been known for about 40 years. You want to minimize what schedulers call the "makespan" (the total time until the last job is done = total time there is work being done) in a 2-machine flow shop. Back in the 50's, Johnson derived an optimal rule, and it is VERY simple: Denote the processing times of the i'th job on machines 1 and 2 as a(i) and b(i), respectively. Now, look at the table of a(i) and b(i) values, and find the smallest number. If this smallest number is an "a" (say a(k)), then schedule job k first; if the smallest number is a "b" (say b(k)), schedule job k last. (If several jobs have "a's" that are the smallest numbers, any one of them can come first, and similarly if several jobs have "b's" that are smallest. Also, if it should happen that there is a job whose a and b are both the smallest numbers in the table, this job should be either first, or last---it doesn't matter which). Remove the job scheduled in the above and repeat (where, in later steps, "first" and "last" refer to the remaining jobs, so if a job J has been scheduled first in some previous step, a new job scheduled "first" comes after J---but first in the list still unscheduled). Your improved schedule above is optimal, and is obtainable using Johnson's rule (breaking some ties arbitrarily). There are several books treating such matters; look under the topics "scheduling", "machine scheduling", "flow shop scheduling", etc. > > Thanks in advance. > > John Bradley > > Assistant Chief of Production > Damo Systems, Ltd. > > -----------== Posted via Deja News, The Discussion Network ==---------- > http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own