OPRE 6385: Scheduling

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: chandra@utdallas.edu
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

Introduction
- Definitions
- Taxonomy of Problems
Simple Problems: Adjacent Pairwise Exchange and its Applications
- Single Machine
1. Weighted Completion Time and WSPT Rule
2. Maximum Lateness and EDD Rule
3. Maximum Tardiness and EDD
4. Two Machine Flow Shop -- Makespan
Parallel Machines: Classification Scheme
- Machine Based
  - Identical
  - Uniform Speeds
  - Unrelated
- Divisibility Based
  - Nondivisible = Nonpreemptive
  - Divisible -- but on the same machine
  - Nonsimultaneous Divisibility -- possibly on several machines
  - Simultaneous Divisibility
- Objective Function
  - Makespan
  - Total Flow Time = Average Flow Time
  - Due Date Based Objectives
- Open Shops
  - Two Machine Nonpreemptive Makespan
  - Preemptive Makespan
Miscellaneous Easy Problems
- Number Tardy on Single Machine
- Job Shop with Two Machines
Problems with Precedence Constraints
- Makespan
  - Tree Constrained Unit Execution Time Nonpreemptive
  - Two Machine Unit Execution Time Nonpreemptive
  - Application of the above to non-UET Preemptive Schedules
- Weighted Total Flow Time
  - Decomposition
  - Trees
Complexity Theory
- Two Machine Nonpreemptive Makespan
- Total Tardiness
- Two Machine Weighted Completion Time Nonpreemptive
- Fully Polynomial Approximation Scheme
Polynomial Approximation Algorithm -- Bin Packing
Branch and Bound, Neighbourhood Searches
- Traveling Salesman Problem
- Dynamic Programming
On-line Algorithms (See this also:) Uniform Machines On-line Algorithms

Assignments

Presentation Topics

Click here to go back ...