Scheduling deteriorating jobs to minimize makespan

✍ Scribed by Wieslaw Kubiak; Steef van de Velde

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 83 KB
• Volume: 45
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/(sici)1520-6750(199808)45:5<511::aid-nav5>3.0.co;2-6

✦ Synopsis

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J j grows by w j with each time unit its start is delayed beyond a given common critical date d. This processing time is p j if J j starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in O(nd ͚ n j Å1 p j ) time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D ú d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n 2 d(D 0 d) ͚ n j Å1 p j ) time and O(nd(D 0 d)) space, the other runs in O(nd ͚ n j Å1 w j (͚ n j Å1 p j ) 2 ) time and O(nd ͚ n j Å1 w j