Industrial Algorithms

Timetable

Module aim (aims)

The course presents the main algorithmic methods applied in production systems, where technological operations are performed using complex algorithms of various kinds. The aim of this course is to familiarize students with the main concepts related to the subject, to present the basic algorithms applied in production systems, and to develop skills that allow the use of these algorithms in practice.The course includes 30 hours of lectures and 30 hours of labs. During the lectures, theoretical foundations and properties of various classes of algorithmic methods applied in production systems are presented. These algorithms are next practiced and implemented in a programming language during the labs. This part of the course is completed by a written test checking the practical knowledge of the algorithms. The written exam completes the course and concerns the general knowledge of the concepts and algorithmic methods discussed in the lectures.

Pre-requisites in terms of knowledge, skills and social competences (where relevant)

The basic knowledge of discrete mathematics, theory of algorithms and complexity theory. Basic programming skills in a programming language such as C or C++.

Syllabus

Week 1: Basic definitions and notions (components of a production system; technological processes and their components; modern manufacturing systems - Airbus, Ford, Hyundai; quality control systems, just-in-time approach; review of basic definitions and notions of theory of algorithms and NP-hardness)

Week 2: Models of production systems (definitions of jobs, operations and machines; parameters describing jobs, operations and machines; main optimality criteria; types of machine environments; the notion of a schedule, main classes of schedules; Adamiecki-Gantt charts; three-field notation)

Week 3: One-machine production systems: Polynomial problems (problems of minimization of the schedule length, maximum lateness, total (weighted) completion time, total cost or number of tardy jobs; algorithms SPT, WSPT, EDD; Lawler’s algorithm; Hodgson-Moore algorithm)

Week 4: One-machine production systems: NP-hard problems (the problem of checking feasibility of a schedule with arbitrary release dates and deadlines; the problem of minimization the maximum lateness in the presence of arbitrary release dates)

Week 5: One-machine production systems: approximation and heuristic algorithms (main type of exact algorithms - enumeration algorithms, branch-and-bound algorithms; the notion of an approximation algorithm and its worst-case ratio; the notion of a heuristic algorithm; the main rules of the conduction of numerical experiments; selected approximation and heuristic algorithms for the problem of minimizing the maximum lateness of a set of independent jobs with non-zero release dates)

Week 6: Parallel-machine production systems: polynomial problems (the main types of parallel machines – identical, uniform, unrelated; the problem of scheduling on two parallel identical machines with arbitrary precedence constraints - Fuji-Kasami-Ninomiya algorithm, Coffman-Graham algorithm; scheduling on parallel identical machines with tree precedence constraints - Hu algorithm; preemptive scheduling on parallel identical machines - McNaughton algorithm; minimizing total completion time on parallel identical machines - algorithm SPT)

Week 7: Parallel-machine production systems: NP-hard problems (the problem of minimizing the schedule length on two parallel identical machines, the problem of minimizing total weighted completion time on two parallel identical machines, the problem of minimizing the schedule length on arbitrary number of parallel identical machines, the problem of minimizing the schedule length on three parallel identical machines for unit-time jobs and arbitrary precedence constraints)

Week 8: Parallel-machine production systems: approximation and heuristic algorithms (algorithm LS for the problem of minimizing the schedule length for dependent jobs and parallel identical machines, the competitive ratio for algorithm LS; algorithms LPT and MULTIFIT for the problem of minimizing the schedule length for independent jobs and parallel identical machines, the worst-case ratios for algorithms LPT and MULTIFIT; selected heuristic algorithms for scheduling dependent jobs on parallel identical or uniform machines)

Week 9: Parallel-machine production systems: approximation schemes (the notion of an approximation scheme, schemes of PTAS and FPTAS type; the main methods of the construction of approximation schemes; selected examples of approximation schemes for the problem of minimizing the schedule length for independent jobs and two parallel identical machines)

Week 10: Dedicated-machine production systems: polynomial problems (main types of dedicated machines - flow shop, open shop, job shop; jobs vs. operations; the problem of minimizing the schedule length for two-machine flow shop system and independent jobs - Johnson algorithm and its variants; dominated machine in the problem of minimizing the schedule length for three-machine flow shop and independent jobs; the problem of minimizing the schedule length for two-machine open shop system and independent jobs - Gonzalez-Sahni algorithm; polynomial cases of the problem of minimizing the schedule length for two-machine job shop system - Jackson algorithm)

Week 11: Dedicated-machine production systems: NP-hard problems (the problem of minimizing the schedule length for three machines of flow shop system and independent jobs; the problem of minimizing the schedule length for three machines of open shop system and independent jobs; the problem of minimizing the schedule length for two machines of job shop system and independent jobs; Giffler-Thompson algorithm for multiple machines of job shop system)

Week 12: Dedicated-machine production systems: approximation and heuristic algorithms (the problem of minimizing the schedule length for multiple machines of flow shop system and independent jobs - Campbell-Dudek-Smith algorithm, the worst-case ratio of Campbell-Dudek-Smith algorithm; heuristic algorithms by Gupta and Palmer for the problem of minimizing the schedule length for multiple machines of flow shop system and independent jobs; selected heuristic algorithms for the problem of minimizing the schedule length and multiple machines of job shop system)

Week 13: Dedicated-machine production systems: meta-heuristic algorithms (basic definitions and notions related to local search algorithms - globally optimal solution, locally optimal solution, solution neighbourhood; selected examples of local search algorithms; the notion of a meta-heuristic algorithm; basic definitions and notions related to meta-heuristic algorithms - population of solutions, solution generation, stop condition, taboo list, crossing and mutation of solutions; main types of meta-heuristic algorithms - taboo search, simulated annealing, genetic algorithms, evolutionary algorithms; methodology of conduction of numerical experiments with meta-heuristic algorithms) Week 14: Selected new models of production systems (scheduling on machines with non-availability periods - the notion of non-availability period; the main types of preemption related to non-availability periods; the problems of minimizing the schedule length and total completion time for one-machine with a single non-availability period; scheduling with learning effects - the notion of a learning effect; the main models of learning effect; one-machine problems of minimizing the schedule length and total completion time with a learning effect)

Week 15: Selected new models of production systems (time-dependent scheduling - the notion of time-dependent job processing times; main types of functions describing time-dependent job processing times; one-machine time-dependent scheduling problems with minimizing the schedule length, total completion time and maximum lateness for proportional and linear job processing times; two-machine problems of time-dependent scheduling with minimizing the schedule length and proportional and linear job processing times; agent scheduling - the notion of an agent and agent scheduling; description of set of jobs of an agent; main types of agent scheduling problems; selected one-machine agent scheduling problems with minimizing the schedule length and total completion time; selected multiple-machine agent scheduling problems with minimizing the schedule length and total completion time)

Reading list

A. Agnetis, J-C. Billaut, S. Gawiejnowicz, D. Pacciarelli, A. Soukhal, Multiagent Scheduling, Springer, 2014.P. Brucker, Scheduling Algorithms, Springer, 1995.G. Chryssolouris, Manufacturing Systems: Theory and Practice, 2nd ed., Springer, 2006.M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.S. Gawiejnowicz, Models and Algorithms of Time-Dependent Scheduling, Springer, 2020.D. Hochbaum, ed., Approximation Algorithms for NP-hard Problems, PWS Publishing, 1998.T.E. Morton, D. Pentico, Heuristic Scheduling Systems, John Wiley & Sons, 1993.C.H. Papadimitiou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 5th ed., Springer, 2016.R.G. Parker, Deterministic Scheduling Theory, Chapman and Hall, 1995.V.V. Vazirani: Approximation Algorithms, Springer, 2003.