Single machine scheduling with set-ups to minimize number of late items: algorithems, complexity and approximation
Author: Kovalyov, M. Y. ; Potts, Christopher N. ; Van Wassenhove, Luk N.INSEAD Area: Technology and Operations Management Series: Working Paper ; 93/82/TM Publisher: Fontainebleau : INSEAD, 1993.Language: EnglishDescription: 13 p.Type of document: INSEAD Working Paper Online Access: Click here Abstract: In the problem of scheduling a single machine to minimize the number of late items, there are N jobs each containing a given number of identical items. Each job may be partitioned into sublots that contain contiguously scheduled items. A set-up time is required before the machine processes the first item in a sublot. Each job has a due date that applies to all of its items, and the objective is to find a schedule which minimizes the number of late items. The problem is shown to be (binary) NP-hard, even for the case of unit processing times and a common due date, although it is pseudopolynomially solvable| Item type | Current location | Collection | Call number | Status | Date due | Barcode | Item holds |
|---|---|---|---|---|---|---|---|
|
Digital Library | Available | BC000915 |
In the problem of scheduling a single machine to minimize the number of late items, there are N jobs each containing a given number of identical items. Each job may be partitioned into sublots that contain contiguously scheduled items. A set-up time is required before the machine processes the first item in a sublot. Each job has a due date that applies to all of its items, and the objective is to find a schedule which minimizes the number of late items. The problem is shown to be (binary) NP-hard, even for the case of unit processing times and a common due date, although it is pseudopolynomially solvable
Digitized
There are no comments for this item.