Show The Graduate Center Menu

Sequencing and Scheduling

1 Course Rationale


Scheduling is a decision-making process that is used on a regular basis in many manufacturing

and services industries. Sequencing and scheduling problems are motivated by allocation

of limited resources to tasks over time. The goal is to nd an optimal allocation where

optimality is dened by some problem specic objective. Thousands of scheduling problems

and models have been studied and analyzed and various algorithms and methodologies have

been applied to those problems.


2 Course Description


This is a graduate-level course on sequencing and scheduling. It emphasizes various types of

solutions to scheduling problems and models, including the computational complexity of the

problems and models, optimal polynomial time algorithms, approximation algorithms, exact

algorithms, Linear Programming solution, Mixed Integer Programming solutions, heuristics,

metaheuristics, and so on. Application areas will include manufacturing scheduling, crew

scheduling in the construction site, nursing scheduling in the hospital, supply chain man-

agement, transportation, and so on. Students are expected to have a solid background in

the analysis of algorithms, computational complexity, discrete mathematics, and elementary

linear optimization.


3 Topic List


Topics include but are not limited to:

  • Introduction: foundation denitions, classic scheduling models, and their representations
  • classical single machine scheduling problems and various solutions: classical polynomial time algorithms, approximation algorithms, branch-and-bound algorithms, linear programming, etc.
  • classical parallel machine scheduling problems, such as load-balancing etd.
  • scheduling in ow shop, job shop, open shop
  • multi-criteria scheduling
  • scheduling subject to machine unavailability
  • scheduling in Supply Chain
  • Introduction to more advanced topics (e.g., scheduling with processing set constraints, batch processing machine scheduling, scheduling in health care)


4 Learning Objectives


Students who successfully complete this course will be able to:

  • Describe the machine environment, job constraints, objective optimization for a given scheduling problem
  • Model the scheduling prolems using  α|β|γ  representation
  • Understand and prove the hardness of some classical scheduling problems.
  • Apply polynomial time algorithm, approximation algorithm, etc to solve the covered scheduling problems
  • Design branch-and-bound algorithm for scheduling problems
  • Evaluate the complexity of an approach to a specic problem and its realistic impact
  • Describe and design heuristics and metaheuristics for the scheduling problems

The course has a general goal providing a capability for sequencing and scheduling re-

search that models a real-world problem with appropriate machine/job/objective representa-

tions, identies or constructs algorithms (from theoretical methodology to empirical study)

to address it, and implements, tests, and evaluates alternative solution(s) to it.


5 Accessment

  • Class participation 10% will asses both applied and theoretical topics
  • Assignments 60% will assess the theoretical topics
  • Term project (presentation and report) 30% will assess the applied topics