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

Céline Swennenhuis (ALGO, TU Eindhoven) | December 13 | A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
by Zdeněk Hanzálek 11 Dec '23

11 Dec '23

Dear scheduling researcher, We are delighted to announce the talk given by Céline Swennenhuis (ALGO, TU Eindhoven). The title is "A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints". The seminar will take place on Zoom on Wednesday, December 13 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98061412979?pwd=UVVmTnhnOHpiMUg2bW5pVFlHSENXdz09 Meeting ID: 980 6141 2979 Passcode: 208805 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. In a classical scheduling problem, we are given a set of n jobs of unit length along with precedence constraints, and the goal is to find a schedule of these jobs on m identical parallel machines that minimizes the makespan. Using the standard 3-field notation, it is known as Pm|prec, p_j=1|Cmax. Settling the complexity of Pm|prec, p_j=1|Cmax even for m=3 machines is, together with Subgraph Isomorphism, among the last two open problems from the book of Garey and Johnson [GJ79] for which the computational complexity remains a mystery. We present an algorithm for this problem that runs in (1 + n/m)^{O(√(nm))} time, which is subexponential when m=o(n). For m=3, this equals a runtime of 2^{O(√(n)log(n))} time. The next talk in our series will be in January. Stay tuned. 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

Maria Elena Bruni (Uni of Calabria) | November 29 | Enhancing project resilience: a risk-averse approach to payment delays
by Zdeněk Hanzálek 27 Nov '23

27 Nov '23

Dear scheduling researcher, We are delighted to announce the talk given by Maria Elena Bruni (Uni of Calabria). The title is " Enhancing project resilience: a risk-averse approach to payment delays ". The seminar will take place on Zoom on Wednesday, November 29 at 14:00 UTC. Please check carefully the summer/winter time change in your country. Join Zoom Meeting https://cesnet.zoom.us/j/92922491900?pwd=TU9uWlpSSHJxSjlnUitxcjdDWkR3UT09 Meeting ID: 929 2249 1900 Passcode: 781666 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The onset of the pandemic and the conflict in Europe have disrupted our society, supply chains, and economies. The effects of these global shocks are evident in every type of project - whether related to the energy transition, the renewal of transport infrastructure, or the construction industry- impacted by the highest rates of inflation in more than 30 years and by a significant cash flow crisis. In this complex landscape, delays in payments have become a common risk factor for projects, since they create a time lag between the expenses incurred by the contractor and the progress payments received from the client. The challenges associated with obtaining continuous project finances often place undue financial strain on contractors that may seek loans from financial institutions to maintain their daily operations. These loans must be returned with interest, increasing financing costs, and considerably lowering the Net Present Value. In this talk, we delve into cash flow and project scheduling strategies to mitigate late payment impacts and enhancing project resilience, presenting a distributionally robust risk-averse model that minimizes the financing cost by accurately estimating the amount and timing of the expenses and revenues throughout the project life cycle and foreseeing possible cost overruns and cash flow fluctuations. Joint work with Oncu Hazir. The next talk in our series will be: Céline Swennenhuis (ALGO, TU Eindhoven) | December 13 | A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints. 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

Claire Hanen (Sorbonne U., LIP6) | November 15 | Fixed Parameter Tractability of scheduling dependent typed tasks with time windows
by Zdeněk Hanzálek 13 Nov '23

13 Nov '23

Dear scheduling researcher, We are delighted to announce the talk given by Claire Hanen (Sorbonne U., LIP6). The title is " Fixed Parameter Tractability of scheduling dependent typed tasks with time windows ". The seminar will take place on Zoom on Wednesday, November 15 at 14:00 UTC. Please check carefully the summer/winter time change in your country. Join Zoom Meeting https://cesnet.zoom.us/j/98132802131?pwd=aUpBNHpxNkUvV0tZbTcxemZFK3JBUT09 Meeting ID: 981 3280 2131 Passcode: 130657 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. This talk discusses the parameterized complexity of scheduling problems, assuming precedence constraints, time windows and typed tasks resource constraints. We recall the usual parameters used for scheduling problems and focus on a parameter suitable for problems with time windows, the pathwitdth of the underlying interval graph. We present three results involving this parameter. First we show a fixed parameter tractable (FPT) algorithm for a scheduling problem with unit processing times. Then, a para-NP-Hardness result assuming arbitrary processing times and finally we outline a FPT algorithm for this problem by considering two parameters. Authors: Claire Hanen and Alix Munier-Kordon. The next talk in our series will be: Maria Elena Bruni (Uni of Calabria) | November 29 | Enhancing project resilience: a risk-averse approach to payment delays. 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

Yumei Huo (CUNY) | November 1 | Sublinear Space and Sublinear Time Algorithms for the Scheduling Problems.
by Zdeněk Hanzálek 30 Oct '23

30 Oct '23

Dear scheduling researcher, We are delighted to announce the talk given by Yumei Huo (CUNY). The title is " Sublinear Space and Sublinear Time Algorithms for the Scheduling Problems ". The seminar will take place on Zoom on Wednesday, November 1 at 14:00 UTC. Please check carefully the summer/winter time change in your country. Join Zoom Meeting https://cesnet.zoom.us/j/98815907109?pwd=QlUvQWV2a0k1M2ZKMEN1cW8xanN4dz09 Meeting ID: 988 1590 7109 Passcode: 224328 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Our research focuses on algorithmic big data solutions for scheduling problems, with a goal of devising efficient algorithm design principles in two key areas: sub-linear space algorithms and sub-linear time algorithms. The sub-linear space algorithm design aims to develop streaming algorithms that can approximate the optimal solution in just a few passes (often just one) over the data, utilizing limited space. On the other hand, the sub-linear time algorithm design strives to develop sampling algorithms that can approximate the optimal solution using a small portion of the input data and operate within sub-linear time. The next talk in our series will be: Claire Hanen (Sorbonne U., LIP6) | November 15 | Fixed Parameter Tractability of scheduling dependent typed tasks with time windows. 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

Dirk Briskorn (Uni of Wuppertal) | October 18 | Single-machine scheduling with an external resource
by Zdeněk Hanzálek 16 Oct '23

16 Oct '23

Dear scheduling researcher, We are delighted to announce the talk given by Dirk Briskorn (Uni of Wuppertal). The title is "Single-machine scheduling with an external resource". The seminar will take place on Zoom on Wednesday, October 18 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96860317751?pwd=OHZBVlpHMlp4clNSTU4wNmRVL2VkZz09 Meeting ID: 968 6031 7751 Passcode: 635870 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We study a single-machine scheduling problem with an external resource, which is rented for a non-interrupted period. Jobs that need this external resource are executed only when the external resource is available. There is a cost associated with the scheduling of jobs and a cost associated with the duration of the renting period of the external resource. We look at four classes of problems with an external resource: a class of problems where the renting period is budgeted and the scheduling cost needs to be minimized, a class of problems where the scheduling cost is budgeted and the renting period needs to be minimized, a class of two-objective problems where both, the renting period and the scheduling cost, are to be minimized, and a class of problems where a linear combination of the scheduling cost and the renting period is minimized. We provide a thorough complexity analysis (NP-hardness proofs and (pseudo-)polynomial algorithms) for different members of these four classes. The next talk in our series will be: Yumei Huo (CUNY) | November 1 | Sublinear Space and Sublinear Time Algorithms for the Scheduling Problems. 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

Kan Fang (Tianjin University) | October 4 | Single machine scheduling in additive manufacturing with two-dimensional packing constraints
by Zdeněk Hanzálek 02 Oct '23

02 Oct '23

Dear scheduling researcher, We are delighted to announce the talk given by Kan Fang (Tianjin University). The title is "Single machine scheduling in additive manufacturing with two-dimensional packing constraints". The seminar will take place on Zoom on Wednesday, October 4 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/97361696066?pwd=Z2hBcFFNZzArQWFPd3YyR1cwUzZIQT09 Meeting ID: 973 6169 6066 Passcode: 950886 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 focus on a single machine scheduling in additive manufacturing, in which parts can be produced simultaneously in a batch with two-dimensional packing constraints, and the objective is to minimize the makespan. In order to solve this problem, we propose an approximation algorithm with constant approximation ratio, and develop a combinatorial Benders decomposition based exact algorithm with various Benders cuts and acceleration strategies. We also conduct extensive computational experiments to test the performance of our proposed solution approaches. The next talk in our series will be: Dirk Briskorn (Uni of Wuppertal) | October 18 | Single-machine scheduling with an external resource. 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

Kan Fang (Tianjin University) | October 4 | Single machine scheduling in additive manufacturing with two-dimensional packing constraints
by Zdeněk Hanzálek 22 Sep '23

22 Sep '23

Dear scheduling researcher, We are delighted to announce the talk given by Kan Fang (Tianjin University). The title is "Single machine scheduling in additive manufacturing with two-dimensional packing constraints". The seminar will take place on Zoom on Wednesday, October 4 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/97361696066?pwd=Z2hBcFFNZzArQWFPd3YyR1cwUzZIQT09 Meeting ID: 973 6169 6066 Passcode: 950886 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 focus on a single machine scheduling in additive manufacturing, in which parts can be produced simultaneously in a batch with two-dimensional packing constraints, and the objective is to minimize the makespan. In order to solve this problem, we propose an approximation algorithm with constant approximation ratio, and develop a combinatorial Benders decomposition based exact algorithm with various Benders cuts and acceleration strategies. We also conduct extensive computational experiments to test the performance of our proposed solution approaches. The next talk in our series will be: Dirk Briskorn (Uni of Wuppertal) | October 18 | Single-machine scheduling with an external resource. 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

Tami Tamir (Reichman Uni) | June 21 | Scheduling with Machine-Dependent Priority Lists
by Zdeněk Hanzálek 19 Jun '23

19 Jun '23

Dear scheduling researcher, We are delighted to announce the talk given by Tami Tamir (Reichman Uni). The title is "Scheduling with Machine-Dependent Priority Lists". The seminar will take place on Zoom on Wednesday, June 21 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/93107274739?pwd=ZzI0Y0RGYmtvaXhwdG5JZDQ4dDJQUT09 Meeting ID: 931 0727 4739 Passcode: 666002 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 natural, yet challenging variant of the parallel machine scheduling problem in which each machine imposes a preferential order over the jobs and schedules the jobs accordingly once assigned to it. We study the setting in which a centralized authority assigns the jobs to machines, as well as the associated non-cooperative game in which jobs are controlled by selfish agents who independently choose which machine to use. In the talk, I will define the model, highlight the differences from other well-analyzed job-scheduling optimization problems and coordinated mechanisms, and present some of our results for several natural objectives (e.g., Makespan, lateness, total completion-time minimization) As we show, having machine-dependent priority lists dramatically affects both the computational complexity of the problem and the equilibrium inefficiency. Joint work with Vipin Ravindran Vijayalakshmi and Marc Schroder. The next talk in our series will in September. 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

Vikram Tiwari (Vanderbilt Uni) | June 7 | Surgery Scheduling: Research and Practice
by Zdeněk Hanzálek 05 Jun '23

05 Jun '23

Dear scheduling researcher, We are delighted to announce the talk given by Vikram Tiwari (Vanderbilt University). The title is "Surgery Scheduling: Research and Practice". The seminar will take place on Zoom on Wednesday, June 7 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96890046173?pwd=bjYzLzkzSUJMU1ZCMWhka2h4RjRqdz09 Meeting ID: 968 9004 6173 Passcode: 999261 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Scheduling of surgeries is a complex process that involves simultaneous scheduling of not only several resources (staff, room, equipment, supplies, instruments), but also building flexibility in capacity-reservation policies to accommodate most types of patient classes. In the case of trauma centers this complexity increases even more due to the need for dynamic rescheduling of elective surgeries as emergency surgeries arrive randomly. In practice, these issues are tackled every day in a ‘non-optimal / heuristic’ way. Recent research in this area has shown the potential of implementing modified priority rules. In contrast to trauma centers, ambulatory surgery centers only perform elective surgeries and have a lower cost structure. Their profitability is therefore dependent upon efficient use of capacity. Recent research has modeled these as Hybrid Flow Shops and solved the capacity planning problem using easy to implement heuristics. This talk will also discuss some new avenues of operating room scheduling that have not yet been researched by academics. The next talk in our series will be: Tami Tamir (Reichman Uni) | June 21 | Scheduling with Machine-Dependent Priority Lists. 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

Erwin Pesch (Uni of Siegen) | May 24 | Conflict-Free Crane Scheduling in a Seaport Terminal.
by Zdeněk Hanzálek 22 May '23

22 May '23

Dear scheduling researcher, We are delighted to announce the talk given by Erwin Pesch (University of Siegen). The title is "Conflict-Free Crane Scheduling in a Seaport Terminal". The seminar will take place on Zoom on Wednesday, May 24 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98592826019?pwd=L1RRMkQ2Q0I4bjN4MzdFVUxLMjlqZz09 Meeting ID: 985 9282 6019 Passcode: 464787 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 focus on a container dispatching and conflict-free yard crane routing problem that arises at a storage yard in an automated, maritime container terminal. A storage yard serves as an intermediate buffer for import/export containers and exchanges containers between water- and landside of a maritime terminal. The problem is in which order and by which crane the containers are transported in order to minimize the makespan and prevent crane interferences. First, we limit our attention to incoming containers only that are positioned by twin cranes. Containers are assigned to the cranes according to different policies. We show that some cases are polynomially solvable. Approximation algorithms with guaranteed absolute and relative deviations from the optimum are devised for others. The results translate for the case of outgoing containers. In the second part we consider two rail mounted gantry cranes of different sizes, with the possibility to cross each other, that perform inbound, outbound and housekeeping requests. We solve this problem to optimality by a branch-and-cut approach that decomposes the problem into two problem classes and connects them via logic-based Benders constraints. The next talk in our series will be: Vikram Tiwari (Vanderbilt Uni) | June 7 | Surgery Scheduling: Research and Practice. 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