✦ LIBER ✦

The counting complexity of a simple scheduling problem

✍ Scribed by Gerardo Berbeglia

Publisher: Elsevier Science
Year: 2009
Tongue: English
Weight: 780 KB
Volume: 37
Category: Article
ISSN: 0167-6377
DOI: 10.1016/j.orl.2009.05.004

No coin nor oath required. For personal study only.

✦ Synopsis

Let T be a set of tasks. Each task has a non-negative processing time and a deadline. The problem of determining whether or not there is a schedule of the tasks in T such that a single machine can finish processing each of them before its deadline is polynomially solvable. We prove that counting the number of schedules satisfying this condition is #P-complete.

📜 SIMILAR VOLUMES

Complexity of a scheduling problem with

Complexity of a scheduling problem with controllable processing times

✍ Byung-Cheon Choi; Joseph Y.-T. Leung; Michael L. Pinedo 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 766 KB

We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem.

Complexity of the job insertion problem

Complexity of the job insertion problem in multi-stage scheduling

✍ Arjen P.A. Vestjens; Marc Wennink; Gerhard J. Woeginger 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 127 KB

The complexity of a cyclic scheduling pr

The complexity of a cyclic scheduling problem with identical machines and precedence constraints

✍ A. Munier 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 589 KB

The complexity of counting homeomorphs

✍ Graham Farr; Colin McDiarmid 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 202 KB

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

The complexity of two group scheduling p

The complexity of two group scheduling problems

✍ Jacek Blazewicz; Mikhail Y. Kovalyov 📂 Article 📅 2002 🏛 Springer US 🌐 English ⚖ 94 KB

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