Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime

Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime

0.00 Avg rating0 Votes
Article ID: iaor20163650
Volume: 19
Issue: 5
Start Page Number: 547
End Page Number: 561
Publication Date: Oct 2016
Journal: Journal of Scheduling
Authors: , ,
Keywords: scheduling, production, combinatorial optimization
Abstract:

In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime‐optimal schedules, called the LD algorithm, has a simple worst‐case performance bound: 5 m 2 4 m 1 equ1 , where m is the number of machines. We study the structure of potential minimal counterexamples to this conjecture, provide some new tools and techniques for the analysis of such algorithms, and prove that to verify the conjecture, it suffices to analyze the following case: for every m 4 equ2 , n { 4 m , 5 m } equ3 , where n is the number of jobs.

Reviews

Required fields are marked *. Your email address will not be published.