Last updated on Jan 29, 2014

Announcements:

Schedule:

Contents:

Sequencing and scheduling problems are motivated by allocation of limited resources over time. The goal is to find an optimal allocation where optimality is defined by some problem specific objective. In this course, deterministic scheduling will be studied in great detail. Different performance criteria will be studied including makespan, total completion time, total weighted completion time, lateness, tardiness, the total number of tardy jobs, total tardiness, etc. We will cover different types of machine environments including single machine, parallel machine, flow shop, job shop, and open shop. Except classical scheduling problems, we may also cover different scheduling models such as multi-criteria scheduling problems, scheduling with limited machine availability, and online scheduling etc. For each specific problem, we either introduce the optimal polynomial time algorithm if it is in P, or give the binary/unary NP-hard proof and/or existing approximation algorithms if it is NP-hard or strong NP-hard. We will introduce Linear programming, Mixed Integer programming, exact algorithms, and some heuristic or meta-heuristic techniques for the very complicated scheduling problems.

Required Textbook: Scheduling: Theory, Algorithms, and Systems 4th edition by Michael L. Pinedo, ISBN-10: 1461419867 | ISBN-13: 978-1461419860.

Reference: Handbook of Scheduling Algorithms, Models, and Performance Analysis Edited by Joseph Y-T. Leung. CHAPMAN & HALL/CRC COMPUTER and INFORMATION SCIENCE SERIES

• The exams may test on material covered only in class and on material covered only in the reading assignments.
  
  Your grade will be based approximately, as follows. These percentages are tentative and subject to change.

   0% - Homeworks (Homeworks will be given but not counted towards the final grade; they are for preparing exams.)
  
  
  25% - Two Quizzes
  
  35% - Midterm Exam #1
  
  40% - Research Work