One Machine Generalized Precedence Constrained Scheduling

Abstract

We investigate one-machine scheduling problems subject to generalized precedence constraints. A precedence constraint specifies that the first of a pair of jobs must be completed before the second can begin. Under our generalized notion, not only must the first job be completed before the second can begin, but also, the difference between the start time of the second job and the completion time of the first job must fall in a given pair-dependent interval. The left endpoint of this interval if greater than zero, specifies a minimum delay and the right endpoint, if finite, specifies a maximum delay between the two jobs. To our knowledge, this dissertation contains the first explicit identification of generalized precedence constraints as we have defined them. As such, it represents the first systematic treatment of generalized precedence constrained scheduling

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1992
Accession Number
ADA265420

Entities

People

  • Erick D. Wi Kum

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • C4I
  • Human Systems

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Dynamic Programming
  • Equations
  • Gantt Charts
  • Inequalities
  • Mathematics
  • New York
  • Notation
  • Operations Research
  • Scheduling (Production)
  • Systems Engineering

Readers

  • Computational Modeling and Simulation
  • Computer Networking
  • Parallel and Distributed Computing.