Report

A Study on Two-machine Flowshop Scheduling Problem with an Availability Constraint Team: Tianshu Guo Yixiao Sha Jun Tian The General Problem A machine may not always be available in the scheduling period Stochastic – breakdown Deterministic – preventive maintenance Our problem Deterministic Environment – unavailable time is known in advance Two-machine Problem – one machine is always available Resumable Jobs – if a job cannot finish before the unavailable period of a machine then the hob can continue after the machine is available again A.C. on M1 – Johnson’s Rule (H1) Apply Johnson’s algorithm on F2/r-a(M1)/Cmax problem Divide the n-hob set into two disjoint subsets, S1 and S2, where S1 = { Ji : pi1 <= pi2 } and S2 = { Ji : pi1 > pi2 } Order the jobs in S1 in the non-decreasing order of pi1 and those jobs in S2 in the non-increasing order of pi2 Sequence jobs in S1 first, followed by S2 (CH1 – C*)/C* ≤ 1, and the bound is tight. A.C. on M1 – An Improved Heuristic (H2) 1. Use Johnson’s Rule to schedule the jobs and compute the corresponding makespan MK1 2. Schedule jobs in non-increasing order of pi2/pi1 and find the corresponding makespan MK2 Let t be the earliest time that M2 starts to be busy until MK2 Let Jk be the job starts at t on M2 3. Same order as in 2 but make Jk the first job in the sequence MK3 Let CH2 = min {MK1, MK2, MK3 } (CH2 – C*)/C* ≤ 1/2 An Example of H2 Job M1 M2 M2/M1 A 4 20 5 B 50 60 1.2 C 80 120 1.5 1. A -> B -> C 2. A -> C -> B No availability constraint imposed M1 0 4 M2 4 24 54 134 54 114 134 M1 254 M2 04 4 24 M1 not available from 30 to 40 M1 0 4 30 40 64 M2 4 24 64 M1 144 124 144 264 M2 134 84 204 84 0 4 30 40 94 4 24 94 144 154 M1 not available from 90 to 105 M1 0 4 M2 4 24 54 90 105 54 M1 149 114 149 269 M2 04 4 24 84 90 105 84 264 274 149 204 264 A.C. on M2 – Johnson’s Rule (H3) Apply Johnson’s algorithm on F2/r-a(M2)/Cmax problem (CH3 – C*)/C* ≤ 1/2 Consider an instance with n jobs, p11 = p21 = pn-1,1 = 1, p12 = p22 = pn-1,2 = 1, and pn,1 = n, pk+1,2 = 1. Also s2 = n, t2 = 2n. Apply H3 to this instance we may get a sequence Jn, J1, J2,…,Jn-1 with CH3 = 3n, while the optimal solution is J1, J2, …,Jn-1 ,Jn, with C* = 2n+1. (CH3 – C*)/C* approaches ½ as n -> ∞ A.C. on M2 –Improved Heuristic (H4) 1. Use Johnson’s Rule to schedule the jobs and compute the corresponding makespan MK1 2. Schedule jobs in non-increasing order of pi2/pi1 and find the corresponding makespan MK2 Let CH4 = min {MK1, MK2}, then (CH2 – C*)/C* ≤ 1/3 Consider an instance with n jobs, p11 = p21 = pn-1,1 = 1, p12 = p22 = pn-1,2 = 1, and pn,1 = n, pn,2 = n. Also s2 = n, t2 = 2n. Apply H4 to this instance we may get a sequence Jn, J1, J2,…,Jn-1 with CH4 = 4n-1, while the optimal solution is J1, J2, …,Jn-1 ,Jn, with C* = 3n. (CH3 – C*)/C* approaches ½ as n -> ∞ Summary of H1 – H4 Heuristic r-a() Makespan Error Bound H1 M1 MK1 1 H2 M1 min {MK1, MK2, MK3} 1/2 H3 M2 MK1 1/2 H4 M2 min {MK1, MK2} 1/3 In H2, we are unable to show the 1/2 bound is tight, but the following instance shows the bound cannot be better than 1/3 Consider an instance with n jobs, p11 = p12 = 1, p21 = p22 = p31 = p32 = k, and s1 = 2k, t1 = 3k. Steps 1 and 2 yields J1-J2-J3, with C = 3k+1+k = 4K +1. Then let J3 be Jk and apply step 3 . The result: J3-J1-J2, with C = 3k+1+k = 4k+1. The optimal solution is J2-J3-J1, with C* = 3k+1+1. (CH2 – C*)/C* approaches 1/3 as n -> ∞ HI—improved version of H2 Reduce error bound to 1/3 C* Where It Has Been Improved Put 2 jobs with longest processing time on M2 in front instead of 1 job as new σ3. With pk ≤ s1, new scheme σ4 is derived from σ2 with Jk moved to the slot right before s1. With pk ≥ s1, new scheme σ5 combines this fact with Johnson’s Rule and σ2. New σ3 Maximum 2 jobs that have long processing time on M2 in optimal schedule. Thus we can possibly put these 2 jobs in the front of sequence. This may result in improved error bound. New σ4 Proved a hidden fact that there is an optional schedule with Jk finishes before s1, not otherwise. Proven fact that the qk determines the error bound of σ2 algorithm. Adjust position of Jk is an option. New σ5 S1={ jobs with longer processing time on M2 but less than pk } S2={ jobs except for Jk and S1 } Proved that there is an optimal solution with all jobs in S1 are scheduled before Jk followed by S2. Since Jk finishes after t1 on M1, use Johnson’s. Order: σ2, Jk, Johnson’s Rule