Title

Weighted Tardiness for the Single Machine Scheduling Problem: An Examination of Precedence Theorem Productivity

Document Type

Article

Publication Date

1-2013

Publication Source

Computers & Operations Research

Abstract

Earlier research by Kanet [11] has provided a number of new theorems for deciding precedence between pairs of jobs for 1∣∣ΣwjTj. The theorems supplant those of Rinnooy Kan, Lageweg, and Lenstra [16]. Presented here are the results of an analysis of the marginal benefit these new theorems provide over the earlier versions of Rinnooy Kan et al. Results show that the new theorems can provide noteworthy improvements in the ability to discover precedence relations between job pairs. For a large set of problem instances the new theorems uncovered up to 8% more precedence relations than the original theorems of Rinnooy Kan et al. The improvement in the productivity in discovering precedence relations shows to be dependent on the coefficient of variation of the distribution of job weights. Logical application of the theorems is to include them in search procedures and/or heuristic approaches to 1||ΣwjTj. One such heuristic based on the theorems is provided here in which the solutions to a large set of sample problems are within 8–12% of the optimum.

Inclusive pages

91–97

ISBN/ISSN

0305-0548

Comments

Permission documentation is on file.

Publisher

Elsevier

Volume

40

Issue

1

Peer Reviewed

yes

Link to Full Text

Share

COinS