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

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

0.00 Avg rating0 Votes
Article ID: iaor19971838
Country: Netherlands
Volume: 72
Issue: 1
Start Page Number: 74
End Page Number: 81
Publication Date: Jan 1994
Journal: European Journal of Operational Research
Authors:
Abstract:

The paper deals with a single-machine scheduling problem with release times, delivery times and controllable job processing times. It is assumed that the cost of performing a job is a linear function of its processing time, and the total schedule cost to be minimized is the total processing cost plus maximum completion time cost. In consequence, the processing order of jobs and their processing times are decision variables. A (ρ+1/3)-approximation algorithm for the problem is provided, where ρ is the worst-case performance bound of a procedure for solving the pure sequencing problem.

Reviews

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