𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Open shop scheduling problems with late work criteria

✍ Scribed by Jacek Błażewicz; Erwin Pesch; Małgorzata Sterna; Frank Werner

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
354 KB
Volume
134
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

The paper concerns the application of a non-classical performance measure, a late work criterion (Y; Yw), to scheduling problems. It estimates the quality of the obtained solution with regard to the duration of the late parts of tasks not taking into account the quantity of this delay. The paper provides the formal deÿnition of the late work parameter, especially in the shop environment, together with its practical motivation. It contains general complexity studies and the results of investigating open-shop scheduling cases, i.e. two polynomial time algorithms for problems O | pmtn; ri | Yw and O2 | di = d | Y , as well as the binary NP-hardness proof for O2 | di = d | Yw.

📜 SIMILAR VOLUMES

Solving the open shop scheduling problem
Solving the open shop scheduling problem
✍ Ulrich Dorndorf; Erwin Pesch; Toàn Phan-Huy 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 128 KB

Only few exact solution methods are available for the open shop scheduling problem. We describe a branch-and-bound algorithm for solving this problem which performs better than other existing algorithms. The key to the e ciency of our algorithm lies in the following approach: instead of analysing an

Note: Open-shop scheduling with release
Note: Open-shop scheduling with release dates to minimize maximum lateness
✍ Hans Kellerer; Thomas Tautenhahn; Gerhard Woeginger 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 295 KB 👁 2 views

We present the first polynomial-time algorithm for an open-shop problem with unit execution times, arbitrary release dates, and due dates. The objective is to minimize maximum lateness. 0 I995 John Wiley & Sons. Inc.

Open shop scheduling with maximal machin
Open shop scheduling with maximal machines
✍ George J. Kyparisis; Christos Koulamas 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 698 KB

## The objective of this paper is to develop polynomial algorithms for the open shop makespan problem. It is shown that when a machine majorizes all other machines and the ith largest processing time on that machine is at least as large as the processing times of all operations on machines i throu