- Scheduling seminar - list.iid.ciirc.cvut.cz

Maciej Drozdowski (Poznan UT)| Oct 23 | Scheduling divisible loads
by Zdeněk Hanzálek 14 Oct '24

14 Oct '24

Dear scheduling researcher, We are delighted to announce the talk given by Maciej Drozdowski (Poznan UT). The title is "Scheduling divisible loads". The seminar will take place on Zoom on Wednesday, October 23 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96350506239?pwd=QlxrGyT3FiSaawN9eQqBj7u8pdF5IU.1 Meeting ID: 963 5050 6239 Passcode: 185009 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. In this talk divisible load theory (DLT) will be introduced. The theory is a scheduling and computer performance model applicable in data-parallel applications. Its basic assumption is that the computing work can be divided into pieces of arbitrary sizes and these pieces can be processed independently in parallel. In the talk we will proceed from the basic formulation of divisible load scheduling on heterogeneous system to a formulation for multi-installment divisible load processing in heterogeneous system with hierarchical memory and energy constraints. NP-hardness of various DLT scheduling problem variants will be considered. Application of DLT as isoefficiency maps visualizing parallel processing performance relationships will be demonstrated. The next talk in our series will be: Hugo Chareyre (Artelys) | November 6 | Operational scheduling in automotive industry For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Ender Ozcan (Uni of Nottingham) | Jun 12 | Machine Learning meets Selection Hyper-heuristics
by Zdeněk Hanzálek 10 Jun '24

10 Jun '24

Dear scheduling researcher, We are delighted to announce the talk given by Ender Ozcan (Uni of Nottingham). The title is "Machine Learning meets Selection Hyper-heuristics". The seminar will take place on Zoom on Wednesday, June 12 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91588200395?pwd=sySE3R77BKsPZfaOOQ8O7EyeuhfLT3.1 Meeting ID: 915 8820 0395 Passcode: 557258 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Hyper-heuristics are powerful search methodologies that operate on low level heuristics or heuristic components to tackle computationally hard optimisation problems. The current state-of-the-art in hyper-heuristic research contains classes of algorithms that focus on intelligently selecting or generating a suitable heuristic for a given situation. Hence, there are two main types of hyper-heuristics: selection and generation hyper-heuristics. A typical selection hyper-heuristic chooses a low-level heuristic and applies it to the current solution at each step of a search, before deciding whether to accept or reject the newly created solution. Generation hyper-heuristics, in contrast, automatically build heuristics or heuristic components during the search process. Machine learning is revolutionising various fields, and its integration with hyper-heuristics holds immense potential. This talk will first offer a concise overview of hyper-heuristics, followed by illustrative case studies demonstrating how we have successfully applied machine learning to automatically design more effective selection hyper-heuristics. The next talk in our series will be: For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
by Zdeněk Hanzálek 27 May '24

27 May '24

Dear scheduling researcher, We are delighted to announce the talk given by Matthias Mnich (TU Hamburg). The title is " New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines ". The seminar will take place on Zoom on Wednesday, May 29 at 13:00 UTC. Please be aware of summertime. Join Zoom Meeting https://cesnet.zoom.us/j/93008634528?pwd=b0JuTWdLaVpINFM3VGZPVFUydzIydz09 Meeting ID: 930 0863 4528 Passcode: 089440 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest absolute coefficient in any constraint. - Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3∥A∥_1) + \sqrt{log(∥A∥_1)}), where ∥A∥_1 denotes the 1-norm of the constraint matrix A. Our upper bounds also hold with ∥A∥_1 replaced by \sqrt{m∆}, which improves on the previously best constants in the linearized form. - Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + ε)-approximation for Q||Cmax on N jobs in time 2^{O(1/ε log^3(1/ε) log(log(1/ε)))} + O(N), which improves exponentially over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation with small support size. The next talk in our series will be: Ender Ozcan (Uni of Nottingham) | Jun 12 | Machine Learning meets Selection Hyper-heuristics For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
by Zdeněk Hanzálek 21 May '24

21 May '24

Dear scheduling researcher, We are delighted to announce the talk given by Matthias Mnich (TU Hamburg). The title is " New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines ". The seminar will take place on Zoom on Wednesday, May 29 at 13:00 UTC. Please be aware of summertime. Join Zoom Meeting https://cesnet.zoom.us/j/93008634528?pwd=b0JuTWdLaVpINFM3VGZPVFUydzIydz09 Meeting ID: 930 0863 4528 Passcode: 089440 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest absolute coefficient in any constraint. - Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3∥A∥_1) + \sqrt{log(∥A∥_1)}), where ∥A∥_1 denotes the 1-norm of the constraint matrix A. Our upper bounds also hold with ∥A∥_1 replaced by \sqrt{m∆}, which improves on the previously best constants in the linearized form. - Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + ε)-approximation for Q||Cmax on N jobs in time 2^{O(1/ε log^3(1/ε) log(log(1/ε)))} + O(N), which improves exponentially over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation with small support size. The next talk in our series will be: Ender Ozcan (Uni of Nottingham) | Jun 12 | Machine Learning meets Selection Hyper-heuristics For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

André Rossi (Universite PSL) | April 3 | Maximizing stability of assembly line balancing schedules under uncertain task duration
by Zdeněk Hanzálek 02 Apr '24

02 Apr '24

Dear scheduling researcher, We are delighted to announce the talk given by André Rossi (Universite PSL). The title is " Maximizing stability of assembly line balancing schedules under uncertain task duration ". The seminar will take place on Zoom on Wednesday, April 3 at 13:00 UTC. Please be aware of summertime. Join Zoom Meeting https://cesnet.zoom.us/j/99589658637?pwd=NFU5Y255VUl1WjYwYUxpaFZGV3JUUT09 Meeting ID: 995 8965 8637 Passcode: 782996 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We consider a variant of the simple assembly line balancing problem in which the number of workstations and the cycle time are fixed, but some tasks are subjected to uncertainty (processing times can increase). The purpose is to maintain the schedule feasibility when the duration of tasks increases. To achieve this, we consider two stability measures (to be maximized): the stability radius, and the stability factor, that correspond to different types of task duration increase. The scheduling problem is formulated as a mixed integer linear program, and this formulation is strengthened by an upper bound and a heuristic. More specifically, the allocation intervals of the tasks, that are based on precedence constraints, are narrowed, which in turn are used to improve the results of the heuristic and the mixed integer linear programming formulation. The next talk in our series will be: Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Pieter Smet (KU Leuven) | March 20 | Robustness in personnel rostering.
by Zdeněk Hanzálek 18 Mar '24

18 Mar '24

Dear scheduling researcher, We are delighted to announce the talk given by Pieter Smet (KU Leuven). The title is "Robustness in personnel rostering". The seminar will take place on Zoom on Wednesday, March 20 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/99775148608?pwd=UkgwT25wRXpHL1k3dzJhbkFqc2pkdz09 <https://cesnet.zoom.us/j/99775148608?pwd=UkgwT25wRXpHL1k3dzJhbkFqc2pkdz09> Meeting ID: 997 7514 8608 Passcode: 885832 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. In this talk, we study the problem of generating personnel rosters that are robust with respect to disruptions caused by employee absenteeism. If an employee unexpectedly becomes absent, they must be replaced by another employee. This in turn may affect the working hours of other employees, creating an undesirable ripple effect that changes a large part of the roster. We investigate how making use of on-call duties may avoid such large perturbations. We begin by first introducing a metric to quantify the robustness of a roster, which is then used to generate sufficiently robust rosters. In the second part of this talk, we discuss the conditions under which machine learning can lead to better solutions. A novel methodology is presented to determine the minimum prediction performance required to outperform the non-data-driven rostering approach. The next talk in our series will be: André Rossi (Universite PSL) | April 3 | Maximizing stability of assembly line balancing schedules under uncertain task duration For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Laurent Perron (Google France) | March 6 | The CP-SAT solver.
by Zdeněk Hanzálek 04 Mar '24

04 Mar '24

Dear scheduling researcher, We are delighted to announce the talk given by Laurent Perron (Google France). The title is "The CP-SAT solver". The seminar will take place on Zoom on Wednesday, March 6 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98573827806?pwd=UDRqdzYwbktrR29RQk02MVZqMUtkUT09 Meeting ID: 985 7382 7806 Passcode: 287789 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The CP-SAT solver is developed by the Operations Research team at Google and is part of the OR-Tools open-source optimization suite. It is an implementation of a purely integral Constraint Programming solver on top of a SAT solver using Lazy Clause Generation. It draws its inspiration from the chuffed solver, and from the CP 2013 plenary by Peter Stuckey on Lazy Clause Generation. The CP-SAT solver improves upon the chuffed solver in two main directions. First, it uses a simplex alongside the SAT engine. Second, it implements and relies upon a portfolio of diverse workers for its search part. The use of the simplex brings the obvious advantages of a linear relaxation on the linear part of the full model. It also started the integration of MIP technology into CP-SAT. This is a huge endeavour, as MIP solvers are mature and complex. It includes presolve -- which was already a part of CP-SAT --, dual reductions, specific branching rules, cuts, reduced cost fixing, and more advanced techniques. It also allows the tight integration of the research from the Scheduling on MIP community along with the most advanced scheduling algorithms. This has enabled breakthroughs in solving and proving hard scheduling instances of the Job-Shop problems and Resource Constraint Project Scheduling Problems. Using a portfolio of different workers makes it easier to try new ideas and to incorporate orthogonal techniques with little complication, except controlling the explosion of potential workers. These workers can be categorized along multiple criteria like finding primal solutions -- either using complete solvers, Local Search or Large Neighborhood Search --, improving dual bounds, trying to reduce the problem with the help of continuous probing. This diversity of behaviors has increased the robustness of the solver, while the continuous sharing of information between workers has produced massive speedups when running multiple workers in parallel. All in all, CP- SAT is a state-of-the-art solver, with unsurpassed performance in the Constraint Programming community, breakthrough results on Scheduling benchmarks (with the closure of many open problems), and competitive results with the best MIP solvers (on purely integral problems). The next talk in our series will be: Pieter Smet (KU Leuven) | March 20 | Robustness in personnel rostering. For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Nils Boysen (University of Jena) | February 21 | Scheduling in the e-commerce era: New scheduling problems in order fulfilment and warehousing.
by Zdeněk Hanzálek 20 Feb '24

20 Feb '24

Dear scheduling researcher, We are delighted to announce the talk given by Nils Boysen (University of Jena). The title is " Scheduling in the e-commerce era: New scheduling problems in order fulfilment and warehousing". The seminar will take place on Zoom on Wednesday, February 21 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95552422876?pwd=Y1lPM2RVeTR4cmh5anMyUXUzWVBGZz09 Meeting ID: 955 5242 2876 Passcode: 739068 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Driven by the success of e-commerce, today's warehouses are evolving into fully automated fulfillment factories. Many of them follow the parts-to-picker paradigm, using mobile shelf-lifting robots or conveyors to deliver stock keeping units (SKUs) to stationary order pickers working in picking workstations. This talk aims to structure and review the family of fulfillment-related scheduling problems that arise in this environment: On the input side, the sequence in which totes of SKUs are delivered to a workstation must be synchronized with the orders that are being assembled there at the same time on the output side. In this way, a more efficient fulfillment process can be achieved, and the bin supply system can be relieved. This talk classifies the family of slightly different order fulfillment scheduling problems that arise with different workstation setups in alternative warehouses. This classification scheme is used to survey the existing literature, analyze the computational complexity, and systematically quantify the gains of alternative workstation setups. The talk also highlights valuable future research ideas for this emerging area of scheduling research. The next talk in our series will be: Laurent Perron (Google France) | March 6 | The CP-SAT solver. For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Ceyda Oğuz (Koç University) | February 7 | A Matheuristic for the Generalized Order Acceptance and Scheduling Problem
by Zdeněk Hanzálek 05 Feb '24

05 Feb '24

Dear scheduling researcher, We are delighted to announce the talk given by Ceyda Oğuz (Koç University). The title is "A Matheuristic for the Generalized Order Acceptance and Scheduling Problem". The seminar will take place on Zoom on Wednesday, February 7 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95550377545?pwd=NUNRWlhjZHRzZDg5aWRCOTA1S3RzQT09 Meeting ID: 955 5037 7545 Passcode: 003354 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Firms operating on a make-to-order basis may not satisfy the entire demand due to limited capacity and tight delivery times. This necessitates selecting only part of customer orders to maximize the total revenue, which gives rise to the order acceptance and scheduling (OAS) problems. In this study, we investigate a generalized version of the OAS (GOAS) problem originating from a real- life setting. Due to several components of the problem, such as release times, due dates, deadlines and sequence dependent setup times, finding an exact solution to GOAS problem, that determines which orders to accept and how to schedule them simultaneously to maximize the revenue, in reasonable time even in a single machine environment is difficult. Hence, we develop an effective and efficient matheuristic, which consists of a time-bucket based mixed integer linear programming model, a variable neighborhood search algorithm and a tabu search algorithm, for the GOAS problem. Computational results show that the proposed matheuristic outperforms the state-of-the- art algorithms developed for the GOAS problem. The boundary of optimally solved instance size is pushed further and near optimal solutions are obtained in reasonable time for instances falling beyond this boundary. Joint work with İstenç Tarhan. The next talk in our series will be: Nils Boysen (University of Jena) | February 21 | Scheduling in the e-commerce era: New scheduling problems in order fulfilment and warehousing. For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Klaus Heeger (Ben Gurion University) | January 24 | Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by Zdeněk Hanzálek 22 Jan '24

22 Jan '24

Dear scheduling researcher, We are delighted to announce the talk given by Klaus Heeger (Ben Gurion University). The title is " Minimizing the Weighted Number of Tardy Jobs is W[1]-hard ". The seminar will take place on Zoom on Wednesday, January 24 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/92404235122?pwd=cFVxSVBPS28wS3dhYVQ5WVhJcEVkUT09 Meeting ID: 924 0423 5122 Passcode: 536766 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We consider the 1 || ∑ wj Uj problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both in theory and practice. We prove that 1 || ∑ wj Uj is W[1]-hard with respect to the number of different processing times in the input, as well as with respect to the number of different weights in the input. This, along with previous work, provides a complete picture for 1 || ∑ wj Uj from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH). Based on joint work with Danny Hermelin. The next talk in our series will be: Ceyda Oğuz (Koç University) | February 7 | A Matheuristic for the Generalized Order Acceptance and Scheduling Problem. For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0