Heuristics for scheduling problems with an unavailability constraint and position‐dependent processing times

Heuristics for scheduling problems with an unavailability constraint and position‐dependent processing times

0.00 Avg rating0 Votes
Article ID: iaor20122895
Volume: 62
Issue: 4
Start Page Number: 908
End Page Number: 916
Publication Date: May 2012
Journal: Computers & Industrial Engineering
Authors: ,
Keywords: scheduling, combinatorial optimization
Abstract:

We study a single machine scheduling problem, where the machine is unavailable for processing for a pre‐specified time period. We assume that job processing times are position‐dependent. The objective functions considered are minimum makespan, minimum total completion time and minimum number of tardy jobs. All these problems are known to be NP‐hard even without position‐dependent processing times. For all three cases we introduce simple heuristics which are based on solving the classical assignment problem. Lower bounds, worst case analysis and asymptotic optimality are discussed. All heuristics are shown numerically to perform extremely well.

Reviews

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