One Machine Scheduling With Delayed Precedence Constraints.

Abstract

We study the one machine scheduling problem with release and delivery times and the minimum makespan objective, in the presence of constraints that for certain pairs of jobs require a delay between the completion of the first job and the start of the second (delayed precedence constraints). This problem arises naturally in the context of the Shifting Bottleneck Procedure for the general job shop scheduling problem, as a relaxation of the latter, tighter than the standard one machine relaxation. The paper first highlights the difference between the two relaxations through some relevant complexity results. Then it introduces a modified Longest Tail Heuristic whose analysis identifies those situations that permit efficient branching. As a result, an optimization algorithm is developed whose performance is comparable to that of the best algorithms for the standard one machine problem. Embedding this algorithm into a modified version of the Shifting Bottleneck Procedure that uses the tighter one machine relaxation discussed here results in a considerable overall improvement in performance on all classes of job shop scheduling problems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1992
Accession Number
ADA261797

Entities

People

  • Alkis Vazacopoulos
  • Egon Balas
  • Jan K. Lenstra

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Evolutionary Algorithms
  • Heuristic Methods
  • Intervals
  • Job Shop Scheduling
  • Mass Spectrometry
  • Mathematics
  • Military Research
  • Scheduling (Production)
  • Schools
  • Sequences
  • Standards
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Industrial Economics
  • Systems Analysis and Design