Single‐machine scheduling problems with time and position dependent processing times

Single‐machine scheduling problems with time and position dependent processing times

0.00 Avg rating0 Votes
Article ID: iaor20116874
Volume: 186
Issue: 1
Start Page Number: 345
End Page Number: 356
Publication Date: Jun 2011
Journal: Annals of Operations Research
Authors: , , ,
Keywords: heuristics
Abstract:

We consider single‐machine scheduling problems with time and position dependent job processing times. In many industrial settings, the processing time of a job changes due to either job deterioration over time or machine/worker’s learning through experiences. In the models we study, each job has its normal processing time. However, a job’s actual processing time depends on when its processing starts and how many jobs have completed before its start. We prove that the classical SPT (Shortest Processing Time) rule remains optimal when we minimize the makespan or the total completion time. For problems of minimizing the total weighted completion time, the maximum lateness, and the discounted total weighted completion time, we present heuristic sequencing rules and analyze the worst‐case bounds for performance ratios. We also show that these heuristic rules can be optimal under some agreeable conditions between the normal processing times and job due dates or weights.

Reviews

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