The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

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?

Excerpt from The Algorithm Design Manual: Devising a proper schedule to satisfy a set of constraints is fundamental to many applications. A critical aspect of any parallel processing system is the algorithm mapping tasks to processors. Poor scheduling can leave most of the expensive machine sitting idle while one bottleneck task is performed. Assigning people to jobs, meetings to rooms, or courses to final exam periods are all different examples of scheduling problems.

Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. For this reason, several other catalog problems have a direct application to various kinds of scheduling.

We focus on precedence-constrained scheduling problems for directed acyclic graphs. These problems are often called PERT/CPM, for Program Evaluation and Review Technique/Critical Path Method. Suppose you have broken a big job into a large number of smaller tasks. For each task you know how long it should take (or perhaps an upper bound on how long it might take). Further, for each pair of tasks you know whether it is essential that one task be performed before another. The fewer constraints we have to enforce, the better our schedule can be. These constraints must define a directed acyclic graph, acyclic because a cycle in the precedence constraints represents a Catch-22 situation that can never be resolved.


Implementations

  • JOBSHOP (C) (rating 10)
  • Tablix: Free software for solving timetabling problems (C) (rating 10)
  • LEKIN - Flexible Job-Shop Scheduling System (Binary) (rating 9)
  • ILOG CP: Solve Complex Scheduling and Routing Problems (Binary) (rating 8)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)
  • Discrete Optimization Methods (Pascal) (rating 4)

  • Recommended Books

    Scheduling Algorithms by P. Brucker Handbook of Scheduling: Algorithms, Models, and Performance Analysis by Y-T. Leung and James H. Anderson Scheduling: Theory, Algorithms, and Systems by M. Pinedo
    Intelligent Scheduling by Mark Fox

    Related Links

  • PATAT conference

    Related Problems


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



    This page last modified on 2008-07-10 .
    www.algorist.com