Scheduling jobs with position-dependent processing times

Scheduling jobs with position-dependent processing times

0.00 Avg rating0 Votes
Article ID: iaor20051318
Country: United Kingdom
Volume: 55
Issue: 3
Start Page Number: 257
End Page Number: 264
Publication Date: Mar 2004
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: production
Abstract:

The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.

Reviews

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