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

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

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