Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
7-1-1975
Abstract
The problem of scheduling n jobs on one machine to minimize the weighted number tardy is considered, when job arrival times, processing times, due dates and weights are given constants. It is assumed that jobs may be interrupted at any time, and later resumed without penalty. A taxonomy of special cases for this problem is developed. Polynomial-bounded algorithms are given for some of the special cases and some other special cases are shown to belong to the set of NP-complete problems. A branch-bound solution is presented for the case in which all jobs have the same weight. The algorithm is tested on numerical data and the results are tabulated.
Keywords
Operations research, Scheduling--Mathematical models, Job shops--Management, Production scheduling, Algorithms, Mathematical optimization, NP-complete problems, Branch and bound algorithms
Publication Title
Dissertation, Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 385 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Dadachanji, Keki R., "Scheduling Intermittently Arriving Jobs to Minimize the Weighted Number Tardy" (1975). Research Reports from the Department of Operations. 497.
https://commons.case.edu/wsom-ops-reports/497