Minimizing the number of tardy jobs on a single machine with batch setup times

Rote Günter and Woeginger Gerhard J.: Minimizing the number of tardy jobs on a single machine with batch setup times. In: Acta cybernetica, (13) 4. pp. 423-429. (1998)

[thumbnail of cybernetica_013_numb_004_423-429.pdf]
Cikk, tanulmány, mű

Download (550kB) | Preview


This paper investigates a single-machine sequencing problem where the jobs are divided into families, and where a setup time is incurred whenever there is a switch from a job in one family to a job in another family. This setup only depends on the family of the job next to come and hence is sequence independent. The jobs are due-dated, and the objective is to find a sequence of jobs that minimizes the number of tardy jobs. The special case of this problem where in every family the jobs have at most two different due dates is known to be A, ''P-coniplete [Bruno & Downey, 1978]. The main result of this paper is a polynomial time algorithm for the remaining open case where in every family all the jobs have the same due date. This case may be formulated as a dual resource allocation problem with a tree-structured constraint system, which can be solved to optimality in polynomial time.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1998
Volume: 13
Number: 4
ISSN: 0324-721X
Page Range: pp. 423-429
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 428-429. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 15:51

Actions (login required)

View Item View Item