CS 6V81 081: Scheduling
ECSS 2.201  ...... Summer 2005..... TR: 10:00 -- 12:45


Instructor: R. Chandrasekaran

Office: ECSN 4.622 (Please Note: This is in the "old" building!!

Phone: (972) 883-2032 E-mail: [email protected]
Office Hours: W
URL: http://www.utdallas.edu/~chandra

Class Room: ECSS 2.201: TR 10:00 -- 12:45

Prerequisites: CS 6363 ; or consent of the instructor.

Grading Scheme

Homework and presentations (Schedule TBA)

Course Objective

This course deals with various problems in the area of scheduling. It is primarily about deterministic job-shop scheduling. The techniques used vary: linear programming, transportation, matching, dynamic programming etc. Complexity issues are discussed along with approximation techniques, branch and bound and other enumeration methods. The course concludes with various heuristics and their properties. Click here to get a copy of the syllabus in postscript format.

Text:

  • Scheduling: Theory, Algorithms, and Systems, M. Pinedo, Second Edition, Prentice Hall, 2002
  • Computer and Job Shop Scheduling Theory, E.G. Coffman (Ed)., J. Wiley 1976
  • Course Outline

    1. Introduction
    2. Simple Problems: Adjacent Pairwise Exchange and its Applications
      1. Weighted Completion Time and WSPT Rule
      2. Maximum Lateness and EDD Rule
      3. Maximum Tardiness and EDD
      4. Two Machine Flow Shop -- Makespan
    3. Parallel Machines: Classification Scheme
    4. Miscellaneous Easy Problems
    5. Problems with Precedence Constraints
    6. Complexity Theory
    7. Polynomial Approximation Algorithm -- Bin Packing
    8. Branch and Bound, Neighbourhood Searches
    9. On-line Algorithms (See this also:) Uniform Machines On-line Algorithms

    Assignments


    Click here to go back ...