✦ LIBER ✦

The complexity of two group scheduling problems

✍ Scribed by Jacek Blazewicz; Mikhail Y. Kovalyov

Publisher: Springer US
Year: 2002
Tongue: English
Weight: 94 KB
Volume: 5
Category: Article
ISSN: 1094-6136
DOI: 10.1002/jos.118

No coin nor oath required. For personal study only.

✦ Synopsis

The problems of scheduling groups of jobs under the group technology assumption are studied. The two remaining open questions posed in the literature a decade ago about the computational complexity of these problems (J. Oper. Res. Soc., 1992; 43:395 -406), are answered. The parallel machine problem to minimize the total job completion time is proved to be NP-hard in the strong sense, even if group set-up times are equal to zero. A dynamic programming algorithm is presented to solve this problem, which is polynomial if the number of machines is ÿxed. The two-machine open-shop problem to minimize the makespan is proved to be NP-hard in the ordinary sense, even if there are zero group set-up times and equal job processing times on both machines. It is shown that the latter problem under the condition that any group can be split into batches does not reduce to the problem where the splittings are not allowed, i.e. the group technology assumption is satisÿed.

📜 SIMILAR VOLUMES

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

Complexity of vehicle routing and schedu

Complexity of vehicle routing and scheduling problems

✍ J. K. Lenstra; A. H. G. Rinnooy Kan 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 371 KB

Complexity of Nonlinear Two-Point Bounda

Complexity of Nonlinear Two-Point Boundary-Value Problems

✍ Bolesław Kacewicz 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 282 KB

We study upper and lower bounds on the worst-case e-complexity of nonlinear two-point boundary-value problems. We deal with general systems of equations with general nonlinear boundary conditions, as well as with second-order scalar problems. Two types of information are considered: standard informa

The Complexity of Scheduling Trees with

The Complexity of Scheduling Trees with Communication Delays

✍ Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 190 KB

We consider the problem of finding a minimum-length schedule on m machines for a set of n unit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, we prove that this problem is NP-complete; second, we derive a linear time algorithm

The Complexity of Two-Point Boundary-Val

The Complexity of Two-Point Boundary-Value Problems with Analytic Data

✍ Arthur G. Werschulz 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 409 KB

Makespan minimization in the two-machine

Makespan minimization in the two-machine flowshop batch scheduling problem

✍ T.C.E. Cheng; B.M.T. Lin; A. Toker 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 2 views

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part-types are to be produced in a flexible manufacturing cell organized into a two-stage production line. The jobs are processed in batches on the first