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/
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/
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/
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/
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/
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/
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/
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/
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/
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/