Planning and scheduling problems occur in many real-world processes. Particularly in industrial processes there are often constraints on the order in which tasks can be performed. This leads to natural, industrially-critical optimization problems. For example, a company might choose to buy many machines to process tasks but then there is a risk that the machines will be underused, which is economically inefficient. On the other hand, too few machines, or an inappropriate ordering of tasks, and machines might spend a significant amount of time standing idle, waiting for the output of other machines. In this course the various mathematical techniques for optimizing planning and scheduling problems are investigated. Various models will be investigated such as single-machine models, parallel-machine models, job-shop models. The complexity of algorithms and models will be emphasized. After completing this course students will understand the mathematics and algorithms associated with modeling and solving planning/scheduling problems. Students will be able to understand under which circumstances different planning/scheduling problems are computationally tractable. The students will be able to solve planning and scheduling problems, using the right technique, in practice.
Prerequisites: none Desired Prior Knowledge: Some experience with optimization (e.g. linear programming) and/or design and analysis of efficient algorithms.