Services must be delivered with high punctuality to be competitive. The classical scheduling theory offers to minimize the total earliness and tardiness of jobs to deliver punctual services. In this study, we developed a fully polynomial-time optimal algorithm to transform a given sequence, the permutation of jobs, into its corresponding minimum cost schedule, the timing of jobs. We provide the necessary and sufficient properties for the optimal scheduling of the sub-sequences of jobs, called clusters. The algorithm first decomposes a sequence into several clusters, and then it applies a recursive scheme to join the clusters and to generate their minimum cost schedules. The complexity status sheds light on our algorithm's competitiveness compared with other state-of-the-art algorithms in the literature.
Citation
1
Article
View Migration from Sequence to Schedule in Total Earliness and Tardiness Scheduling Problem