Module also offered within study programmes:
General information:
Name:
Combinatorial Optimization and Scheduling in Manufacturing and Services
Course of study:
2019/2020
Code:
ZZIP-2-309-n
Faculty of:
Management
Study level:
Second-cycle studies
Specialty:
-
Field of study:
Management and Production Engineering
Semester:
3
Profile of education:
Academic (A)
Lecture language:
English
Form and type of study:
Part-time studies
Course homepage:
 
Responsible teacher:
dr hab. inż. Kaczmarczyk Waldemar (wkaczmar@zarz.agh.edu.pl)
Module summary

This course provides an accessible introduction to scheduling in manufacturing and services: problems, models, methods and tools.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence: is able to
M_K001 acquire knowledge by oneself. ZIP2A_K01 Execution of a project
Skills: he can
M_U001 model and solve standard combinatorial problems in the area of production and operations management. ZIP2A_U04 Execution of a project,
Execution of exercises,
Test
M_U002 identify the type of a production or logistic process, to choose and implement appropriate optimisation model for arising planning or scheduling problem. ZIP2A_U06 Execution of a project,
Execution of exercises,
Test
Knowledge: he knows and understands
M_W001 Mixed Integer Programming modelling techniques, as well as standard scheduling and combinatorial models applied in operations management. ZIP2A_W02, ZIP2A_W06 Execution of a project,
Test
M_W002 scheduling and combinatorial optimisation methods and tools applied in operations management. ZIP2A_W02, ZIP2A_W06 Execution of a project,
Test
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
28 14 0 0 0 0 0 0 0 14 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Social competence
M_K001 acquire knowledge by oneself. + - - - - - - - + - -
Skills
M_U001 model and solve standard combinatorial problems in the area of production and operations management. + - - - - - - - + - -
M_U002 identify the type of a production or logistic process, to choose and implement appropriate optimisation model for arising planning or scheduling problem. + - - - - - - - + - -
Knowledge
M_W001 Mixed Integer Programming modelling techniques, as well as standard scheduling and combinatorial models applied in operations management. + - - - - - - - - - -
M_W002 scheduling and combinatorial optimisation methods and tools applied in operations management. + - - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 125 h
Module ECTS credits 5 ECTS
Udział w zajęciach dydaktycznych/praktyka 28 h
Preparation for classes 42 h
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 15 h
Realization of independently performed tasks 40 h
Module content
Lectures (14h):

Combinatorial Optimization and Scheduling in Manufacturing and Services is an advanced course on combinatorial optimization and mixed integer programming applications in the area of production and operations management.


The course consists of two parts:
1. Combinatorial and Mixed Integer Programming Models.
2. Scheduling Models and Algorithms.

Highlights

  • Mixed integer programming as a practical tool widely used for long- medium- and short-term decision making in manufacturing and service systems.
  • A large class of discrete and combinatorial optimization problems, including the most important production and operations management problems can be modeled as mixed integer linear programs.
  • Many manufacturing and service scheduling problems can be modeled and solved using mixed integer programming.

Content

  1. Introduction to combinatorial optimization and mixed integer programming. Problems with indivisibilities: integer programs for knapsack, bin packing and cutting stock problems.
  2. Mixed integer programs for assignment, traveling salesman and set covering/partitioning problems.
  3. Resource and task allocation problems. Mixed integer programs for machine loading, assembly line balancing and routing problems.
  4. Fixed charge problems. Mixed integer programs for location, production and inventory planning, robotized assembly cell design and loading problems.
  5. Network flow problems.
  6. Optimization on graphs: introduction to the theory of graphs and basic definitions.
  7. Minimum spanning tree, maximum matching, minimum covering problems.
  8. Arc routing problems and MIP models: undirected and directed Chinese postman problems.
  9. Introduction to machine scheduling: classification of scheduling problems, classical assumptions, parameters, optimality criteria, Gantt chart representation.
  10. Computational complexity of combinatorial algorithms. Worst-case bound and analysis of a heuristic algorithm.
  11. Classical single and parallel machine scheduling problems and algorithms. SPT, EDD, LPT, ECT, and other heuristics.
  12. Flow shop scheduling: exact and heuristic approaches, Johnson’s algorithm, Johnson’s type heuristics, B&B approach and MIP models for the flow shop scheduling. Flow shops with intermediate constraints: no store, no wait and a TSP equivalent model.
  13. Job shop scheduling: disjunctive graph model and a MIP approach.

Workshops (14h):

During auditorium classes students discuss and solve selected problems:

  1. Modelling knapsack, bin packing and cutting stock problems.
  2. Asymmetric vs. symmetric TSP.
  3. MIP models for machine loading, assembly line balancing and routing problems.
  4. Modelling location, production and inventory planning, robotized assembly cell design and loading problems.
  5. MIP models for network flow problems.
  6. Algorithms for maximum matching, minimum covering problems.
  7. MIP models for Chinese postman problems.
  8. MIP models for single and parallel machine scheduling.
  9. MIP models for the flow shop scheduling.
  10. MIP models for job shop scheduling.

Additional information
Teaching methods and techniques:
  • Lectures: During the lecture, the lecturer describes and solves various decision-making problems. For this purpose, he uses a whiteboard, multimedia presentation, spreadsheets, simulations, and other means. To stimulate students' activity, the lecturer asks them questions or initiates discussion.
  • Workshops: Students first try to solve the scheduled assignments themselves before each class and then during the class solve the same tasks under the guidance of the lecturer. If necessary, the lecturer suggests next solution steps, corrects mistakes, points out typical mistakes, indicates alternative solutions, provides additional explanations, initiates discussions on the results.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:
  1. All grades are calculated according to the scale compliant with the regulations of the AGH studies (a score of 50% is required to obtain the lowest passing grade).
  2. To complete the auditorium exercises, students have to get a positive total score from all tests and projects. On all tests, all material discussed from the beginning of the semester is valid. The overall rating is determined as a simple average of all grades. Oral answers allow students to get additional points for the overall assessment.
  3. If the student has not achieved a positive grade from any form of classes at the required date, he/she is entitled to write a retake.
Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: No
    – Participation rules in classes: Students listen to the lecture, and if they do not understand something they should ask questions. If the lecturer asks questions or initiates discussion, students should present their opinion. During the lecture, students should make their own notes, especially when solving tasks on the board. The script for each lecture, in the form of a PDF file, is available before the lecture. While discussing its content, notes may be limited to the student's own observations. After the lecture, and sometimes before, students should read the recommended reading material. It is not allowed to record or film a lecture without the consent of the teacher.
  • Workshops:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Before the exercises, students should recall the content of earlier lectures and try to solve the scheduled assignments. During the exercises, when one of the students solves the and on at the whiteboard, others solve them in parallel in their notebooks. Students should report their doubts on whether the solution presented on the whiteboard is correct, ask for additional explanations if they do not understand the solution method.
Method of calculating the final grade:

The final grade is calculated as the average of grades with the following weights:

Grade Weight
Exercises 20%
Project 30%
Tests 50%
Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Absence from lectures or exercises needs to be made up by studying the issues discussed in the classroom with the help of lecture notes available on the e-learning platform. If someone omits the test, then have to write it on the date agreed with the lecturer.

Prerequisites and additional requirements:

Module “Models and Algorithms of Decision Making”

Recommended literature and teaching resources:
  1. H. A. Eiselt, Carl-Louis Sandblom, Operations Research, A Model-Based Approach, Springer, 2013.
  2. T. Sawik (1998): Badania operacyjne dla inżynierów zarządzania. (Operations Research for Industrial Engineers). AGH University Press, Kraków. (textbook in Polish).
  3. T. Sawik (1999): Production Planning and Scheduling in Flexible Assembly Systems. Springer, Berlin.
  4. T. Sawik (2011): Scheduling in Supply Chains Using Mixed Integer Programming. John Wiley & Sons, Inc., Hoboken, NJ (USA).
Scientific publications of module course instructors related to the topic of the module:

Selected publications:

  1. T. Sawik (1999): Production Planning and Scheduling in Flexible Assembly Systems. Springer, Berlin.
  2. T. Sawik (2011): Scheduling in Supply Chains Using Mixed Integer Programming. John Wiley & Sons, Inc., Hoboken, NJ (USA).
  3. Kaczmarczyk, W. (2008). Partial coordination may increase overall costs in supply chains, Decision Making in Manufacturing and Services 2(1-2): 47-62.
  4. Kaczmarczyk, W. (2009b). Practical tips for modelling lot-sizing and scheduling problems, Decision Making in Manufacturing and Services 3(1-2): 37-48.
  5. Kaczmarczyk, W. (2009c). multi-period set-up times in the proportional lot-sizing problem, Decision Making in Manufacturing and Services 3(1-2): 15-35.
  6. Kaczmarczyk, W. (2009d). Inventory cost settings in small bucket lot-sizing and scheduling models, Total Logistic Management 2: 27-36.
  7. Kaczmarczyk, W. (2011). Proportional lot-sizing and scheduling problem with identical parallel machines, International Journal of Production Research 49(9): 2605-2623.
  8. Kaczmarczyk, W., Sawik, T., Schaller, A. Tirpak, T. (2004). Optimal versus heuristic scheduling of surface mount technology lines, International Journal of Production Research 42(10): 2083-2110.
  9. Kaczmarczyk, W., Sawik, T., Schaller, A. he/she Tirpak, T. (2006). Production planning and coordination in customer driven supply chains, Wybrane Zagadnienia Logistyki Stosowanej, Tom 3, Komitet Transportu Polskiej Akademii Nauk, s. 81-89.
Additional information:

-