算法高级教程3.2theschedulingproblem.pptVIP

* Thus A≤ OPT(I) +(1?1/m)tc+1≤(1+(1?1/m)m/(c+1)) OPT(I) =(1+(m-1)/(c+1)) OPT(I) and the bound on the performance ratio follows. Suppose m is fixed and let an ε0 be given. If c is chosen such that 1 + (m ? 1)/(c+1) ≤1+ε thus , then the LPTc rule is a ‘polynomial-time’ scheduling policy with a performance ratio 1 + ε, so it is a PTAS! * Interestingly, a different technique shows that the assumption that m be fixed can be removed. Theorem 3.2.3 (Hochbaum and Shmoys, 1987) There exists an algorithm scheme A(I,ε) such that for any fixed ε 0, A(I,ε) computes an approximate schedule for minimum makespan scheduling on identical machines with performance ratio 1 +ε and runs in time polynomial in |I|. * Homework Exercises: Page 83 4,5 Experiments: Implement LPTc algorithm * problem Job shop scheduling problem The job shop scheduling problem (JSSP) may be stated as follows: jobs are to be processed by machines within a given time period in such way that given objectives are optimized. Each job consists of a specific set of operations which have to be processed according to a given precedence order, the objective is to minimize the makespan. Please design an approximation algorithm for it. * * This is the how we intend to tackle the job shop scheduling problem. Read the slide * Ok, the problem. % Read slide, stress on the highlighted terms JSSP, here on I’ll use this acronym Makespan, we’ll see what this is in a moment We’ll understand why approximation * * Means optimal CMax = maxi,j C*j is its optimal value Read slide This is an illustration of a schedule A job 1 has 4 operations Job2 has 2 operations and job 3 has 3 operations The operations cannot overlap. The operations of a job have a fixed order * The JSSP belongs to a broader class of problems called the General shop scheduling problem Read the slide * We need to introduce the notation from shop scheduling problem because we will use this often to succinctly descr