𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Solving the open shop scheduling problem

✍ Scribed by Ulrich Dorndorf; Erwin Pesch; Toàn Phan-Huy

Publisher
Springer US
Year
2001
Tongue
English
Weight
128 KB
Volume
4
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

✦ Synopsis

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 and improving the search strategies for ÿnding solutions, we focus on constraint propagation based methods for reducing the search space. Extensive computational experiments on several sets of well-known benchmark problem instances are reported. For the ÿrst time, many problem instances are solved to optimality in a short amount of computation time.

📜 SIMILAR VOLUMES

The open shop scheduling problem with a
The open shop scheduling problem with a given sequence of jobs on one machine
✍ Y.M. Shafransky; V.A. Strusevich 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB 👁 2 views

The paper considers the open shop scheduling problem to minimize the makespan, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not a

The complexity of cyclic shop scheduling
The complexity of cyclic shop scheduling problems
✍ Nicholas G. Hall; Tae-Eog Lee; Marc E. Posner 📂 Article 📅 2002 🏛 Springer US 🌐 English ⚖ 190 KB

We consider scheduling problems for shops in which a job set is manufactured repetitively. Jobs are scheduled to minimize the cycle time of the job set, which is equivalent to maximizing the throughput rate. We characterize the complexity of the scheduling problem for several types of job shops. Pol