Paper Info
Title
Common Due-Date Problem: Linear Algorithm for a Given Job Sequence
Abstract
This work presents a study on the general case of the Common Due-Date scheduling problem (CDD). The CDD is a problem of scheduling and sequencing a certain number of jobs with different processing times on a single machine against a common due-date. The objective of the problem is to minimize the total penalty incurred due to earliness or tardiness of the jobs. This work presents a novel property for the CDD which implies that in any given job sequence (also the optimal job sequence) of the CDD the position of the due-date is independent to the processing times of the jobs. Thereafter, we put forward an exact polynomial algorithm to optimize a given job sequence with a run-time complexity of O(n), where n is the number of jobs. Henceforth, we implement our polynomial algorithm in conjunction with a modified Simulated Annealing (SA) algorithm to obtain the optimal or best job sequence. The effectiveness of our approach is evident from our results for the benchmark instances provided in the OR-library.
Year
DOI
Venue
2014
10.1109/CSE.2014.51
Computational Science and Engineering
Keywords
Field
DocType
linear programming,schedules,vectors
Single-machine scheduling,Mathematical optimization,Job shop scheduling,Multiprocessor scheduling,Fair-share scheduling,Computer science,Flow shop scheduling,Least slack time scheduling,Linear programming,Rate-monotonic scheduling
Conference
ISBN
Citations 
PageRank 
978-1-4799-7980-6
0
0.34
References 
Authors
10
3
Name
Order
Citations
PageRank
Jörg Lässig117522.53
Abhishek Awasthi293.27
Oliver Kramer330438.42