SINGLE-MACHINE SCHEDULING WITH DEADLINES TO MINIMIZE THE WEIGHTED NUMBER OF TARDY JOBS

Authors
HARIRI AMA POTTS CN
Citation
Ama. Hariri et Cn. Potts, SINGLE-MACHINE SCHEDULING WITH DEADLINES TO MINIMIZE THE WEIGHTED NUMBER OF TARDY JOBS, Management science, 40(12), 1994, pp. 1712-1719
Citations number
10
Categorie Soggetti
Management,"Operatione Research & Management Science
Journal title
Management science → ACNP
ISSN journal
00251909
Volume
40
Issue
12
Year of publication
1994
Pages
1712 - 1719
Database
ISI
SICI code
0025-1909(1994)40:12<1712:SSWDTM>2.0.ZU;2-Y
Abstract
This paper considers a single machine scheduling problem in which jobs have due dates and deadlines. A job may be completed after its due da te, but not after its deadline, in which case it is tardy. A branch an d bound algorithm is proposed to find a schedule which minimizes the w eighted number of tardy jobs. It uses lower bounds which are derived u sing the dynamic programming state-space relaxation method. Computatio nal experience with test problems having up to 300 jobs indicates that the lower bounds are extremely effective in restricting the size of t he branch and bound search tree.