✦ LIBER ✦

Scheduling to minimize the total compression and late costs

✍ Scribed by T.C.E. Cheng; Zhi-Long Chen; Chung-Lun Li; B.M.-T. Lin

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 101 KB
Volume: 45
Category: Article
ISSN: 0894-069X
DOI: 10.1002/(sici)1520-6750(199802)45:1<67::aid-nav4>3.0.co;2-j

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly.

📜 SIMILAR VOLUMES

Open shop scheduling to minimize the num

Open shop scheduling to minimize the number of late jobs

✍ Christos Koulamas; George J. Kyparisis 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 2 views

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are or

Job-shop scheduling to minimize total wa

Job-shop scheduling to minimize total waiting time

✍ Chu, Chengbin ;Portmann, Marie-Claude 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 538 KB

A note on the complexity of family sched

A note on the complexity of family scheduling to minimize the number of late jobs

✍ T. C. Edwin Cheng; Zhaohui Liu; Yakov M. Shafransky 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 65 KB 👁 2 views

The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and pro

Minimizing the sum of absolute lateness

Minimizing the sum of absolute lateness in single-machine and multimachine scheduling

✍ P. S. Sundararaghavan; Mesbah U. Ahmed 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 424 KB

Scheduling of a single machine to minimi

Scheduling of a single machine to minimize total weighted completion time subject to release dates

✍ Lucio Bianco; Salvatore Ricciardelli 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 764 KB

## Abstract In this paper the __n__/1/__r__~j~ Σ~j~ __w__~__j__~ __C__~__j__~ problem under the assumptions of nonpreemptive sequencing and sequence independent processing times is investigated. After pointing out the fundamental properties, some dominance sufficient conditions among sequences are

Scheduling with tool changes to minimize

Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance

✍ M. Selim Akturk; Jay B. Ghosh; Evrim D. Gunes 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract The machine scheduling literature does not consider the issue of tool change. The parallel literature on tool management addresses this issue but assumes that the change is due only to part mix. In practice, however, a tool change is caused most frequently by tool wear. That is why we c