Industrial Algorithmics

Timetable

Module aim (aims)

• The course presents the main algorithmic methods applied in manufacturing systems, where technological operations are performed using complex algorithms of various kinds. The aim of the course is to familiarize students with the main concepts related to the subject, to present the basic algorithms applied in manufacturing systems, and to learn them how to use 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 manufacturing systems are presented. These algorithms are next practiced and implemented in a programming language during the labs. Lab 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: Fundamentals of manufacturing systems (components of a production system; technological processes and their components; modern manufacturing systems - Airbus, Ford, Hyundai; quality control systems, just-in-time approach)

 

 

 

Week 2: Models of manufacturing systems (definitions of jobs, operations and machines; the main types of parallel machines: identical, uniform, unrelated; the main types of dedicated machines: flow shop, open shop, job shop; parameters of jobs, operations and machines; main optimality criteria; the notion of a schedule; the main classes of schedules; Adamiecki-Gantt charts; scheduling algorithms vs. scheduling rules; three-field notation)

 

 

 

Week 3: Basic definitions and notions (the notion of problem, decision and optimization problems; algorithm and its properties; time and space complexity of algorithms; asymptotic notation; polynomial, pseudo-polynomial and exponential algorithms; main types of exact algorithms: enumeration algorithms, branch-and-bound algorithms; an approximation algorithm, the worst-case and competitive ratio; approximation scheme, approximation schemes of PTAS and FPTAS type; a heuristic algorithm; meta-heuristic algorithms; classes P and NP; NP-complete and NP-hard problems) 

 

 

 

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

 

 

 

Week 5: One-machine 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; the problem of minimizing the weighted number of tardy jobs)

 

 

 

Week 6: Parallel-machine systems: polynomial problems (the problem of scheduling on two parallel identical machines with arbitrary precedence constraints: Fujii-Kasami-Ninomiya’s algorithm, Coffman-Graham’s algorithm; scheduling on parallel identical machines with tree precedence constraints: Hu’s algorithm; preemptive scheduling on parallel identical machines: McNaughton algorithm; minimizing total completion time on parallel identical machines: modified SPT rule)

 

 

 

Week 7: Parallel-machine 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)

 

 

 

Week 8: Parallel-machine systems: approximation algorithms (consequences of NP-hardness; coping with NP-hardness; algorithm LS for the problem of minimizing the schedule length for dependent jobs and parallel identical machines, the competitive ratio of algorithm LS; algorithm LPT, the worst-case ratio of algorithm LPT)

 

 

 

Week 9: Approximation schemes (definition of approximation scheme, PTAS schemes, FPTAS schemes, main methods of the construction of approximation schemes, Sahni’s approximation scheme for the problem of minimizing the schedule length for independent jobs and two parallel identical machines)

 

 

 

Week 10: Dedicated-machine systems: polynomial problems (the problem of minimizing the schedule length for two-machine flow shop system and independent jobs: Johnson’s 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’s algorithm, LAPT rule; polynomial cases of the problem of minimizing the schedule length for two-machine job shop system: Jackson’s algorithm)

 

 

 

Week 11: Dedicated-machine 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)

 

 

 

Week 12: Dedicated-machine systems: approximation algorithms (the problem of minimizing the schedule length for multiple machines of flow shop system and independent jobs: Campbell-Dudek-Smith’s algorithm, the worst-case ratio of Campbell-Dudek-Smith’s algorithm)

 

 

 

Week 13: Modern models of manufacturing systems I (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 14: Modern models of manufacturing systems II (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 jobs of an agent, main types of agent scheduling problems, one-machine agent scheduling problems with minimizing the schedule length and total completion time, parallel-machine agent scheduling problems with minimizing the schedule length and total completion time)

 

 

 

Week 15: Applications of manufacturing system models (classical and modern models, main features of both classes of models, applications of classical models, applications of modern models)

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. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.
• M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 5th ed., Springer, 2016.
• S. Rai, G. Vairaktarakis, NP complete problems and proof methodology, in: C.A. Floudas, P.M. Pardalos (eds.), Encyclopaedia of Optimization, 2nd ed., Springer, 2009, pp. 2675–2682.
• R.G. Parker, Deterministic Scheduling Theory, Chapman and Hall, 1995.
• H. Shachnai , T. Tamir , Polynomial time approximation schemes, in: T.F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC, 2007, Chap. 9.
• V.A. Strusevich, K. Rustogi , Scheduling with Times Changing Effects and Rate-Modifying Activities, Springer, 2017. 
• D.R. Sule, Industrial Scheduling, PWS Publishing Company, 1997. 
• V.S. Tanaev , V.S. Gordon, Y.M. Shafransky , Scheduling Theory: Single-Stage Systems, Kluwer, 1994.
• V.S. Tanaev , Y.N. Sotskov, V.A. Strusevich, Scheduling Theory: Multi-Stage Systems, Kluwer, 1994.
• V.V. Vazirani: Approximation Algorithms, Springer, 2003.