  


WorstCase Performance Analysis of Some Approximation Algorithms for Minimizing Makespan and FlowTime
Peruvemba Sundaram Ravi(praviwlu.ca) 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 LD algorithm, has a simple worstcase performance bound: (5m2)/(4m1) , where m is the number of machines. We study structure of potential minimal counterexamples to this conjecture and prove that the conjecture holds for the cases (i) n > 5m, (ii) m = 2, (iii) m = 3, and (iv) m greater than or equal to 4, n less than or equal to 3m, where n is the number of jobs. We further conclude that to verify the conjecture, it suffices to analyze the following case: for every m greater than or equal to 4, n is either equal to 4m or 5m. Keywords: parallel identical machines, makespan, total completion time, approximation algorithms for scheduling Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Applications  OR and Management Sciences (Scheduling ) Citation: Download: [PDF] Entry Submitted: 12/17/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  