An approximation algorithm for a single-machine scheduling problem with release times and delivery times

An approximation algorithm for a single-machine scheduling problem with release times and delivery times

0.00 Avg rating0 Votes
Article ID: iaor1995530
Country: Netherlands
Volume: 48
Issue: 1
Start Page Number: 69
End Page Number: 79
Publication Date: Jan 1994
Journal: Discrete Applied Mathematics
Authors: ,
Abstract:

The authors consider the scheduling problem in which jobs with release times and delivery times are to be scheduled on one machine. They present a 3/2-approximation algorithm which runs in O(nlogn) time and a new robust lower bound for this problem. The known until the present 3/2-approximation algorithm has O(n2logn) computational complexity.

Reviews

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