1.3.9 Job Scheduling

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A directed acyclic graph G=(V,E) , where the vertices represent jobs and the the edge (u,v) that task u must be completed before task v .

Problem: What schedule of tasks to completes the job using the minimum amount of time or processors?

Implementations

  • Discrete Optimization Methods (Pascal) (rating 4)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)

    Related Problems

  • Bin Packing
  • Edge Coloring
  • Feedback Edge/Vertex Set
  • Matching
  • Topological Sorting
  • Vertex Coloring

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .