Scheduling jobs of equal length: complexity, facets and computational results

Y. Crama, F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

Given are n jobs, which have to be performed on a single machine within a fixed timespan {1,2,…T}. The processing time (or length) of each job equals p, p Є IN. The processing cost of each job is an arbitrary function of its start-time. The problem is to schedule all jobs so as to minimize the sum of the processing costs. This problem is proved to be NP-hard, already for p = 2 and 0—1 processing costs. On the other hand, when T=np + c, with c constant, the problem can be solved in polynomial time. A partial polyhedral description of the set of feasible solutions is presented. In particular, two classes of facet-defining inequalities are described, for which the separation problem is polynomially solvable. Also, we exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions. Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated problem instances.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization. IPCO 1995
EditorsE. Balas, J. Clausen
Place of PublicationBerlin
PublisherSpringer
Pages277-291
Number of pages15
ISBN (Electronic)978-3-540-49245-0
ISBN (Print)978-3-540-59408-6
DOIs
Publication statusPublished - 1995
Externally publishedYes
Event4th International Conference on Integer Programming and Combinatorial Optimizatio (IPCO 1995) - Copenhagen, Denmark
Duration: 29 May 199531 May 1995
Conference number: 4

Publication series

NameLecture Notes in Computer Science
Volume920
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Conference on Integer Programming and Combinatorial Optimizatio (IPCO 1995)
Abbreviated titleIPCO 1995
CountryDenmark
CityCopenhagen
Period29/05/9531/05/95

Keywords

  • Computational complexity
  • Polyhedral description
  • Scheduling

Fingerprint

Dive into the research topics of 'Scheduling jobs of equal length: complexity, facets and computational results'. Together they form a unique fingerprint.

Cite this