CS 6301-008: Scheduling
CB1 1.104  ...... Spring 2020..... TR: 10:00 -- 11:15    

Instructor: R. Chandrasekaran

Office: ECSS 4.611

Phone: (972) 883-2032 E-mail: chandra@utdallas.edu
Office Hours: M: 1:30 -- 3:00 p.m.
URL: http://www.utdallas.edu/~chandra

Class Room: : TR 10:00 -- 11:15

Prerequisites: CS 6363 ; or consent of the instructor.

Grading Scheme

Homework and presentations (Schedule TBA)

In case of expected bad weather, I will record  the class at some other time ( I will let you know if I can) and you can view asynchronously. I am choosing actions with the minimum damage.

Audio-3-31-2020 : https://us-lti.bbcollab.com/recording/3c832b5fcb29407ba755de99671f5b12

Audio-4-2-2020: https://us-lti.bbcollab.com/recording/8bd6fb11b7f64069b237a1b9027c7a69

Audio-4-7-2020: https://us-lti.bbcollab.com/recording/c3aedd8086a246478cbef8ae7596970e

You have to go to elearning -- Blackboard collaborate -- the link is:

https://us.bbcollab.com/guest/1561ae1c170f485bb206d008e0cf2f91

If it works, maybe you all can also give your presentations on this site -- or use Microsoft Teams or Webex -- maybe

Please let me know by emails what you think.

• Flow Shop-Approximation [What I have so far -- 3-24-2020]
• Lec-4-2-2020
• Lec-4-9-2020
• Lec-4-11-2020

Group and Topic list

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:

Course Outline

1. Introduction
   • Definitions
   • Taxonomy of Problems
2. 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
3. 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
   • Flow Shops
4. Miscellaneous Easy Problems
   • Number Tardy on Single Machine
   • Job Shop with Two Machines
   • Tardiness-one-machine
5. 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
6. Complexity Theory
   • Two Machine Nonpreemptive Makespan
   • Total Tardiness
   • Two Machine Weighted Completion Time Nonpreemptive
   • Fully Polynomial Approximation Scheme
7. Polynomial Approximation Algorithm -- Bin Packing
8. Branch and Bound, Neighbourhood Searches
   • Traveling Salesman Problem
   • Dynamic Programming
9. On-line Algorithms (See this also:) Uniform Machines On-line Algorithms

Assignments

• Assignment-1
• Assignment-2
• Presentation Topics

Click here to go back ...