Module also offered within study programmes:
General information:
Name:
Combinatorial Optimization and Scheduling in Manufacturing and Services
Course of study:
2017/2018
Code:
ZZIP-2-003-PR-s
Faculty of:
Management
Study level:
Second-cycle studies
Specialty:
Production Management
Field of study:
Management and Production Engineering
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab. inż. Kaczmarczyk Waldemar (wkaczmar@zarz.agh.edu.pl)
Academic teachers:
dr hab. inż. Kaczmarczyk Waldemar (wkaczmar@zarz.agh.edu.pl)
prof. zw. dr hab. inż. Sawik Tadeusz (sawik@zarz.agh.edu.pl)
Module summary

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: Combinatorial and Mixed Integer Programming Models, and Scheduling Models and Algorithms.

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
M_K001 Students are able to acquire knowledge by oneself. ZIP2A_K03 Test
Skills
M_U001 Students are able to determine basic plans and schedules for typical production and logistic operations. ZIP2A_U02 Test
M_U002 Students are able to identify the type of a production or logistic process, to choose and implement an appropriate optimization model for arising planning or scheduling problem. ZIP2A_U06 Test
Knowledge
M_W001 A student knows Mixed Integer Programming modeling techniques, methods, and tools, as well as standard scheduling and combinatorial models applied in operations management. ZIP2A_W11, ZIP2A_W05, ZIP2A_W10 Test
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
Others
E-learning
Social competence
M_K001 Students are able to acquire knowledge by oneself. - + - - - - - - - - -
Skills
M_U001 Students are able to determine basic plans and schedules for typical production and logistic operations. + + - - - - - - - - -
M_U002 Students are able to identify the type of a production or logistic process, to choose and implement an appropriate optimization model for arising planning or scheduling problem. + + - - - - - - - - -
Knowledge
M_W001 A student knows Mixed Integer Programming modeling techniques, methods, and tools, as well as standard scheduling and combinatorial models applied in operations management. + + - - - - - - - - -
Module content
Lectures:

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.

Auditorium classes:

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. Modeling 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.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 125 h
Module ECTS credits 5 ECTS
Participation in lectures 30 h
Participation in auditorium classes 30 h
Realization of independently performed tasks 30 h
Preparation of a report, presentation, written work, etc. 30 h
Examination or Final test 5 h
Additional information
Method of calculating the final grade:

Exercises 20%, project (case study) 30%, written tests 50%.

Prerequisites and additional requirements:

This course is addressed to postgraduate students of management, engineering, and computer science. Basics of mathematics including logic and algebra are required to participate.

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:
  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).
Additional information:

None