Planning and Scheduling Methods

Overview of the Course

Planning and scheduling concerns decision-making processes that are used on a regular basis in various manufacturing and service industries. The planning and scheduling functions in a company rely on mathematical techniques and heuristic methods to allocate limited resources to the activities that have to be done. This allocation of resources has to be done in such a way that the company achieves its goals. This course focuses on key concepts, methods, tools and best practices of planning and scheduling in manufacturing and services applications. We cover project management and machine/job shop scheduling, economic lot size scheduling and timetabling in transportation. The course illustrates how to apply linear programming and mixed-integer-linear-programming to formulate various planning and scheduling problems in practice and demonstrates how to use solvers and/or heuristics to obtain good solutions and perform analysis. The course offers an excellent start for students that aim for a master project and/or career with the application of planning and scheduling.

The course will be demanding at times, and will require a good preparation of all students. In particular we require that students are willing and able to use mathematical notation and ideas to formulate the planning problems; however, we do not require that students are able to solve the problems. Typically, the intent of formulating the problem in a formal form is to be able to ‘feed’ it to a computer, and let the computer solve the problem.

Upon completion of the course the student is able to:

  1. Extract a planning and scheduling problem from a practical problem description
  2. Formulate and model a Linear-Programming or Mixed-Integer-Linear Programming problem in terms of a suitable modeling language
  3. Identify a suitable solution method (for simple systems a solver, for larger systems heuristics)
  4. Implement the solution method in a solver or some other appropriate software tool
  5. Design heuristics and evaluate performance
  6. Interpret results and perform sensitivity analysis
  7. Read academic papers on scheduling and implement the ideas.

Contact info

Course Material

The course is based on Planning and Scheduling in Manufacturing and Services by M.L. Pinedo [pinedo08:_sched]. Interesting background reading can be found in Chapter 15 of Factory Physics [hopp08:_factor_physic]. In Chapter 16 of Factory Physics it is explained how to use the solver of excel. (Of course, this can also be easily found on the web.)

For your interest: I implemented a number of algorithms of this book in python, c.f., Scheduling. These programs are not part of the course but only serve to illustrate a number of problems of the book.

Organization

We expect students to read the book by him/herself, formulate questions, study the examples in the book very carefully, and try hard to solve the assigned problems. During the sessions we discuss the assigned problems and related ideas. We expect to spend about 1 hour per problem and the theory that relates to it. Hence, we will solve about five problems a week: two during the scheduled lectures, and three during the scheduled tutorials.

All sessions (lectures and tutorials) are compulsory.

From the second session onwards, each student has to hand in the solutions of the problems discussed in the previous session. We will pick out a few of these solutions and discuss these in class. The solutions can be turned in in handwritten format, or in Latex. (We urge students to avoid the equation editor of word at all cost, as it leads to very ugly formulas and it is also very unpractical for scientific work.)

Reading Material and Problems

The course consists of 14 solution and discussion sessions: 7 during the lecture hours and 7 during the tutorials.

The sessions are organized according to the chapters of the book. The the required study material is as follows.

The code examples are not obligatory to study, but some of you might find it interesting to see how to implement some of the algorithms and cases discussed in class, lecture slides, and the book.

1a:

Read: Ch 1: entirely; Ch4: 4.1 (but skip job-on-arc part), 4.2,; Appendix A.1, A.2 up (but not including) to the transportation problem, skip also the examples. We also discuss Section 16.2 of Factory Physics.

Homework for the next session: 4.3, 4.4.a (Reference to Exercise 3.1 should be to Exercise 3.2 rather than 3.1) 4.7. Homework on the lecture slides. You have to implement the LP formulation of the critical path method and the LP for Section 16.2 of Factory Physics.

Examples in Python:

1b:

Read: Ch 2: entirely; Ch4: 4.3, 4.4;

Homework for the next session: 4.4.b-c, 4.6 (Before you tackle this problem, ensure you have an lp solver to tackle the project planning problem, so that this part of the computation can be carried out by the computer), 4.8

Examples in Python:

2a

Read: Ch 3: entirely; Ch4: 4.6, 4.8

Homework for the next session: 4.5, 4.9

Examples in Python:

2b

Read: Ch4: 4.7; Appendix A.4, but not Example A.4.2 (this will be tackled in a later lecture);

Homework for the next session: 4.10, A.1

Examples in Python:

3a

Read: Ch5: 5.1, 5.2, A.5

Homework for the next session: 5.1, 5.2

Examples in Python:

3b

Read: Ch5: 5.3, A.6;

Homework for the next session: 5.3, 5.4, 5.5, A.2

Examples in Python:

4a

Read: Ch5: 5.4, 5.6 skim; Appendix: Example A.4.2

Homework for the next session: 5.6, 5.7

Examples in Python:

4b

Read: Ch5: 5.5, 5.7; Appendix: D1, D2, D3.

Homework for the next session: 5.8, 5.9, 5.10

Examples in Python:

5a

Read: Ch7: 7.1–7.2 Tutorial: Bring a laptop with you as you have to work with the excel solver Homework for the next session: 7.1, 7.2

5b

Read: Ch7: 7.3

Homework for the next session: 7.3, 7.4, 7.5, 7.6

6a

Read: 11.1, 11.2

Homework for the next session: 11.1, 11.2

6b

Read: 13.1, 13.2

Homework for the next session: 13.1, 13.2

7a

Read: 13.3

Exercises: 13.3, 13.4, 13.5

7b

Read: Questions 3 and 4 of the example exam

Exercises: Discussion of Questions 3 and 4

Assignments, Examination and Grading

Students have to complete at least 80% of all problems/assignments of the course before they are allowed to take the final exam. Solutions for the homework should be handed in one week later, e.g., the homework of session 1a is due for session 2a, and so on.

The final exam is open-book (that is, it is allowed to use the book, but nothing but the book) and counted as 100% for the grade of the course.

Students should to be able to use the solver of excel to solve (small) mixed-integer problems. Furthermore, they should be able to use excel to solve the project scheduling problems of Sections 4.2, 4.3 and 4.4, and use excel to support the solution procedures of Chapter 5.