Single Machine Scheduling with Discrete Earliness and Tardiness

dc.contributor.authorHarhalakis, Georgeen_US
dc.contributor.authorNagi, R.en_US
dc.contributor.authorProth, J.M.en_US
dc.description.abstractThis paper considers the problem of scheduling a given set of jobs on a single machine in order to minimize the total weighted earliness and tardiness costs. The scheduling horizon is divided into elementary periods; jobs have due-dates at the end of these periods. All jobs are assumed initially available. Jobs have unique (weighted) early and tardy staircase penalty functions. No preemption of jobs is permitted. and idle time may be inserted. We prove that this problem is NP-complete. Some results relating to job priorities and completion times in an optimal solution are presented. A Mixed Integer Linear Programming (MILP) formulation of this problem is developed. A branch-and-bound scheme that solves the above problem optimally is also presented. Heuristics, derived from simple priority rules, provide an initial upperbound to the search. We develop two lower bound procedures for the remaining jobs to be scheduled at any partial solution state. Numerical results relating to the performance of the branch-and- bound scheme are also presented.en_US
dc.format.extent1512895 bytes
dc.relation.ispartofseriesISR; TR 1992-79en_US
dc.subjectproduction/scheduling en_US
dc.subjectdeterministic sequencingen_US
dc.subjectsingle machine sequencingen_US
dc.subjectearly/tardy problemen_US
dc.subjectManufacturing Systemsen_US
dc.titleSingle Machine Scheduling with Discrete Earliness and Tardinessen_US
dc.typeTechnical Reporten_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1.44 MB
Adobe Portable Document Format