Single machine total tardiness maximization problems: complexity and algorithms

Single machine total tardiness maximization problems: complexity and algorithms

0.00 Avg rating0 Votes
Article ID: iaor20133930
Volume: 207
Issue: 1
Start Page Number: 121
End Page Number: 136
Publication Date: Aug 2013
Journal: Annals of Operations Research
Authors: , ,
Keywords: job shop, order review and release, tardiness
Abstract:

In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the total weighted tardiness maximization problem, we present an NP‐hardness proof and a pseudo‐polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP‐hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.

Reviews

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