Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness

✍ Scribed by Maged M. Dessouky

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 308 KB
• Volume: 34
• Category: Article
• ISSN: 0360-8352
• DOI: 10.1016/s0360-8352(98)00105-3

✦ Synopsis

AbstractÐWe consider the problem of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum lateness. This paper develops a branch-and-bound procedure that optimally solves the problem and introduces six simple single-pass heuristic procedures that approximate the optimal solution. The branch-and-bound procedure uses the heuristics to establish an initial upper bound. On sample problems, the branch-and-bound procedure in most instances was able to ®nd an optimal solution within 100,000 iterations with n 80 and m3. For larger values of m, the heuristics provided approximate solutions close to the optimal values.