Sequencing & Scheduling
As a doctoral faculty in the department of computer science at CUNY Graduate Center, My research interests are in Sequencing and Scheduling, Computational Complexity, Combinatorial Optimization, and Operations Research. And I would like to address my research as applying the theory of Computational Complexity and the techniques of Combinatorial Optimization to analyze and solve the problems which are motivated by practical applications.
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. Many researchers from the computer science field study sequencing and scheduling problems with the focus on analyzing the computational complexity of scheduling problems, designing polynomial time algorithms if the problems are in P or approximation algorithms if the problems are NP-Hard, and designing efficient exact algorithms or heuristics or meta-heuristics for the problems. Students from computer science department can learn how to apply the knowledge of computational complexity and combinatorial optimization to solve scheduling problems.
Sequencing and scheduling can find a lot of applications in many areas such as supply chain, load balancing, takeoffs and landings scheduling in the airport, nurse scheduling in the hospital, etc. As long as resource allocation is concerned, the algorithms and techniques from sequencing and scheduling are needed.
So besides students from computer science department, students from Business School, Transportation Department, Industrial Engineering Department, and Operation Research are also welcome.
Learning Goals & Course Content
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.
There will be one midterm exam, 2 quizzes, and one research project. Around 7th or 8th week and counts 35% of the grade. The quizzes are given in the 5th and 12th in the semester and count 25% of the grade. Research project will be due and presented on the last class, and counts 40% of the grade. Homeworks will be given but not counted towards the final grade; they are for preparing exams.