251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

than its processing time, causing the makespan to be strictly larger than the lower bound. If job jh appears in the schedule after job jk, then the jobs following job jk on machine m are not processed one after another without any idle times in between. After job jh there is an idle time on machine m as the next job has a processing time that is strictly larger than the processing time of job jh. unionsq There exists some similarity between this model and the proportionate \ufb02ow shop model with unlimited intermediate storage. For the case with blocking it also can be shown that the SPT rule minimizes \u2211 Cj . As with \ufb02ow shops with unlimited intermediate storage, a fair amount of research has been done in the development of heuristics for the minimization of the makespan in \ufb02ow shops with limited intermediate storage and blocking. One popular heuristic for Fm | block | Cmax is the Pro\ufb01le Fitting (PF) heuristic, which works as follows: one job is selected to go \ufb01rst, possibly according to some scheme, e.g., the job with the smallest sum of processing times. This job, say job j1, does not encounter any blocking and proceeds smoothly from one machine to the next, generating a pro\ufb01le. The pro\ufb01le is determined by its departure from machine i. If job j1 corresponds to job k, then Di,j1 = i\u2211 h=1 ph,j1 = i\u2211 h=1 phk To determine which job should go second, every remaining unscheduled job is tried out. For each candidate job a computation is carried out to determine the amount of time machines are idle and the amount of time the job is blocked at a machine. The departure epochs of a candidate for the second position, say job j2, can be computed recursively: D1,j2 = max(D1,j1 + p1,j2 , D2,j1) Di,j2 = max(Di\u22121,j2 + pi,j2 , Di+1,j1), i = 2, . . . ,m\u2212 1 Dm,j2 = max(Dm\u22121,j2 , Dm,j1) + pm,j2 The time wasted at machine i, that is, the time the machine is either idle or blocked, is Di,j2 \u2212Di,j1 \u2212pi,j2 . The sum of these idle and blocked times over all m machines is then computed. The candidate with the smallest total is selected as the second job. After selecting the job that \ufb01ts best as the job for second position, the new pro\ufb01le, i.e., the departure times of this second job from the m machines, is computed and the procedure repeats itself. From the remaining jobs in the set of unscheduled jobs the best \ufb01t is again selected and so on. In this description the goodness of \ufb01t of a particular job was measured by the total time wasted on all m machines. Each machine was considered equally 170 6 Flow Shops and Flexible Flow Shops (Deterministic) important. It is intuitive that lost time on a bottleneck machine is worse than lost time on a machine that does not have much processing to do. When mea- suring the total amount of lost time, it may be appropriate to multiply each of these inactive time periods on a given machine by a factor that is proportional to the degree of congestion at that machine. The higher the degree of congestion at a particular machine, the larger the weight. One measure for the degree of congestion of a machine that is easy to calculate is simply the total amount of processing to be done on all the jobs at the machine in question. Experiments have shown that such a weighted version of the PF heuristic works quite well. Example 6.2.5 (Application of the PF Heuristic) Consider again 5 jobs and 4 machines. The processing times of the \ufb01ve jobs are in the tables in Examples 6.1.1 and 6.1.6. Assume that there is zero storage in between the successive machines. Take as the \ufb01rst job the job with the smallest total processing time, i.e., job 3. Apply the unweighted PF heuristic. Each one of the four remaining jobs has to be tried out. If either job 1 or job 2 would go second, the total idle time of the four machines would be 11; if job 4 would go second the total idle time of the four machines would be 15 and if job 5 would be second, the total idle time would be 3. It is clear that job 5 is the best \ufb01t. Continuing in this manner the PF heuristic results in the sequence 3, 5, 1, 2, 4 with a makespan equal to 32. From the fact that this makespan is equal to the minimum makespan in the case of unlimited intermediate storage, it follows that sequence 3, 5, 1, 2, 4 is also optimal in the case of zero intermediate storage. In order to study the e\ufb00ect of the selection of the \ufb01rst job, consider the application of the PF heuristic after selecting the job with the largest total processing time as the initial job. So job 2 goes \ufb01rst. Application of the unweighted PF heuristic leads to the sequence 2, 1, 3, 5, 4 with makespan 35. This sequence is clearly not optimal. || Consider now a \ufb02ow shop with zero intermediate storage that is subject to di\ufb00erent operational procedures. A job, when it goes through the system, is not allowed to wait at any machine. That is, whenever it has completed its processing on one machine the next machine has to be idle, so that the job does not have to wait. In contrast to the blocking case where jobs are pushed down the line by machines upstream that have completed their processing, in this case the jobs are actually pulled down the line by machines that have become idle. This constraint is referred to as the no-wait constraint and minimizing the makespan in such a \ufb02ow shop is referred to as the Fm | nwt | Cmax problem. It is easy to see that F2 | block | Cmax is equivalent to F2 | nwt | Cmax. However, when there are more than two machines in series the two problems are di\ufb00erent. The Fm | nwt | Cmax problem, in contrast to the Fm | block | Cmax problem, can still be formulated as a Travelling Salesman Problem. The intercity distances 6.3 Flexible Flow Shops with Unlimited Intermediate Storage 171 are djk = max 1\u2264i\u2264m ( i\u2211 h=1 phj \u2212 i\u22121\u2211 h=1 phk ) for j, k = 0, . . . , n. When there are more than two machines in series this Trav- elling Salesman Problem is known to be strongly NP-hard. 6.3 Flexible Flow Shops with Unlimited Intermediate Storage The \ufb02exible \ufb02ow shop is a machine environment with c stages in series; at stage l, l = 1, . . . , c, there are ml identical machines in parallel. There is an unlimited intermediate storage between any two successive stages. The machine environment in the \ufb01rst example of Section 1.1 constitutes a \ufb02exible \ufb02ow shop. Job j, j = 1, . . . , n, has to be processed at each stage on one machine, any one will do. The processing times of job j at the various stages are p1j , p2j , . . . , pcj. Minimizing the makespan and total completion time are respectively referred to as FFc || Cmax and FFc || \u2211 Cj . The parallel machine environment as well as the \ufb02ow shop with unlimited intermediate storages are special cases of this machine environment. As this environment is rather complex only the special case with proportionate processing times, i.e., p1j = p2j = · · · = pcj = pj , is considered here. Consider FFc | pij = pj | Cmax. One would expect the LPT heuristic to perform well in the nonpreemptive case and the LRPT heuristic to perform well in the preemptive case. Of course, the LPT rule cannot guarantee an optimal schedule; a single stage (a parallel machine environment) is already NP-hard. The worst case behaviour of the LPT rule when applied to multiple stages in series may be worse than when applied to a single stage. Example 6.3.1 (Minimizing Makespan in a Flexible Flow Shop) Consider two stages with two machines in parallel at the \ufb01rst stage and a single machine at the second stage. There are two jobs with p1 = p2 = 100 and a hundred jobs with p3 = p4 = · · · = p102 = 1. It is clear that in order to minimize the makespan one long job should go at time zero on machine 1 and the 100 short jobs should be processed on machine 2 between time 0 and time 100. Under this schedule the makespan is 301. Under the LPT schedule the makespan is 400. || In a preemptive setting the LRPT rule is optimal for a single stage. When there are multiple stages this is not true any more. The LRPT schedule has the disadvantage that at the \ufb01rst stage