Normal view MARC view

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
Tags: No tags from this library for this title. Add tag(s)
Log in to add tags.
Item type Current location Collection Call number Status Date due
INSEAD Working Paper Digital Library
PDF Available

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.

Log in to your account to post a comment.
Koha 3.18 - INSEAD Library Catalogue
Library Home | Contact Us | What's Koha?