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)
Preview |
Cikk, tanulmány, mű
cybernetica_013_numb_004_423-429.pdf Download (550kB) | Preview |
Abstract
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: | http://acta.bibl.u-szeged.hu/38506/ |
| 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 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/12601 |
Actions (login required)
 |
View Item |
