Resource title

Single machine scheduling with set-ups to minimize number of late items: algorithems, complexity and approximation

Resource image

image for OpenScout resource :: Single machine scheduling with set-ups to minimize number of late items: algorithems, complexity and approximation

Resource description

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

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

application/pdf

Resource resource URL

http://flora.insead.edu/fichiersti_wp/Inseadwp1993/93-82.pdf

Resource license

Copyright INSEAD. All rights reserved