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

Sigrid Knust (Uni of Osnabrück) | November 23 | Synchronous flow shop scheduling problems
by Zdeněk Hanzálek 22 Nov '22

22 Nov '22

Dear scheduling researcher, We are delighted to announce the talk given by Sigrid Knust (Uni of Osnabrück). The title is "Synchronous flow shop scheduling problems". The seminar will take place on Zoom on Wednesday, November 23 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91616587714?pwd=SFJGcnpVbTFSSWFGVWt5WHFwL2xuQT09 Meeting ID: 916 1658 7714 Passcode: 332102 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. A synchronous flow shop is a variant of a non-preemptive permutation flow shop where transfers of jobs from one machine to the next take place at the same time. The processing is organized in synchronized cycles which means that in a cycle all current jobs start at the same time on the corresponding machines. Then all jobs are processed and have to wait until the last one is finished. Afterwards, all jobs are moved to the next machine simultaneously. As a consequence, the processing time of a cycle is determined by the maximum processing time of the operations contained in it. Furthermore, only permutation schedules are feasible, i.e., the jobs have to be processed in the same order on all machines. The goal is to find a permutation of the jobs such that the makespan is minimized. Motivated by a practical application in production planning at a company assembling shelf boards for kitchen elements, we investigate different aspects of synchronous flow shop problems. Especially, we consider the situation of dominating machines, additional resources, setup times and leaving machines idle. The next talk in our series will be in January 2023. 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

Alessandro Agnetis (University of Siena) | November 9 | Scheduling machines subject to unrecoverable failures and other related stochastic sequencing problems
by Zdeněk Hanzálek 07 Nov '22

07 Nov '22

Dear scheduling researcher, We are delighted to announce the talk given by Alessandro Agnetis (University of Siena). The title is " Scheduling machines subject to unrecoverable failures and other related stochastic sequencing problems ". The seminar will take place on Zoom on Wednesday, November 9 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98121270904?pwd=aUxmUk5iNENoU3czUmo1Vzg1b3U2dz09 Meeting ID: 981 2127 0904 Passcode: 729055 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Typical scheduling problems deal with a set of activities (jobs) requiring various resources (machines) to be performed. In most scheduling scenarios, it is assumed that machines are continuously avalable (possibly except in some scheduled maintenance intervals), and this gives rise to problems in which the typical scheduling objectives (makespan, total weighted completion time etc) are pursued. A significantly different scenario arises if machines may actually fail, i.e., (i) while performing a job i, a machine becomes unavailable (e.g. breaks down) with probability \pi_i, and (ii) such failures are unrecoverable, in the sense that from then onwards the machine is lost and so are the jobs already allocated and not yet processed on that machine. If a job i is successfully completed, a reward r_i is attained. In this context, the basic problem is how to assign the jobs to the machines and how to sequence them so that the expected reward is maximized. In this talk we review the main results, discuss relationships with other sequencing problems and point out some open problems. We address the following scenarios. 1) m parallel (identical) machines. While the single-machine case is easy, for two or more machines the problem is hard and various approaches have been proposed to address it. For general m, list scheduling yields a 0.8531-approximate solution. The argument of the proof is similar to the one used by Schwiegelshohn to prove Kawaguchi and Kyan's bound for the minimization of total weighted completion time. 2) In order to hedge against machine failures, one can use job replication. In this case, copies of the same job can be scheduled on different machines, and the reward r_i is attained if at least one copy is successfully completed. Although also this problem is hard for m>=2, relatively simple algorithms provide solutions which are provably close to optimality. 3) This class of sequencing problems is also related to testing problems, as follows. A system consists of n components, each of which can be either functioning or not. Only if all components are functioning, the system is "up". Component i is functioning with probability \pi_i, and testing it costs c_i. As soon as a component that is not functioning is detected, the testing stops (concluding that the system is "down"). The problem is to decide in which order should the components be tested, in order to minimize the expected costs. While the single-tester problem is solved by a simple priority rule, various problem variants can be considered. In particular, if several testers operate in parallel, under time constraints, the problem gets more complicated. While it is NP-hard for three or more testers, its complexity with two testers is still open. The next talk in our series will be: Sigrid Knust (Uni of Osnabrück) | November 23 | Synchronous flow shop 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

Clifford Stein (Columbia Uni) | October 26 | Scheduling with Speed Predictions
by Zdeněk Hanzálek 24 Oct '22

24 Oct '22

Dear scheduling researcher, We are delighted to announce the talk given by Clifford Stein (Columbia Uni). The title is "Scheduling with Speed Predictions". The seminar will take place on Zoom on Wednesday, October 26 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91581329122?pwd=M0M4d2tSMXpvb1NkRGhHOVoxWG5vUT09 <https://cesnet.zoom.us/j/91581329122?pwd=M0M4d2tSMXpvb1NkRGhHOVoxWG5vUT09> Meeting ID: 915 8132 9122 Passcode: 596335 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. We study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. In this talk, we give an algorithm that simultaneously achieves, for any x < 1, a 1 + x approximation when the predictions are accurate and a 2+ 2/x approximation when the predictions are not accurate. We also study special cases and evaluate our algorithms performance as a function of the error. Joint work with Eric Balanski, TingTing Ou and Hao-Ting Wei, all at Columbia. The next talk in our series will be: Alessandro Agnetis (University of Siena) | November 9 | Scheduling machines subject to unrecoverable failures and other related stochastic sequencing 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

Greet Vanden Berghe (KU Leuven) | October 12 | Vehicle routing - a focus on heuristic design
by Zdeněk Hanzálek 10 Oct '22

10 Oct '22

Dear scheduling researcher, We are delighted to announce the talk given by Greet Vanden Berghe (KU Leuven). The title is "Vehicle routing - a focus on heuristic design". The seminar will take place on Zoom on Wednesday, October 12 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98337053582?pwd=WnFNYnVManFScEtaMEw2dE5GSnhJZz09 Meeting ID: 983 3705 3582 Passcode: 503069 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Local search-based algorithms have tended towards incorporating an ever-increasing number of heuristics for different problem classes, for example all sorts of vehicle routing generalizations. These heuristics range from all-purpose `swap' and `insert' to complicated made-to-measure operators. It has become a challenge to determine the impact of individual components on an algorithm's performance. In contrast to targeting generalizing problem extensions, it may be worthwhile to focus on a problem's core when designing a basic optimization heuristic. This talk introduces a recently published local search operator for vehicle routing problems: SISRs. This heuristic is unique insofar as it seeks to induce `spatial' and `capacity' slack during a ruin phase which may subsequently be exploited in an almost-greedy recreate phase. SISRs emerged after a dedicated attempt towards solving the vehicle routing problem's most basic special case, that is the `capacitated VRP'. SISRs' quality is validated by way of demonstrating its performance across a wide and diverse range of VRP generalizations. This confirms that the basic CVRP ruin & recreate heuristic is also effective when applied to more general vehicle problems, including fleet minimization, without the need to design additional problem-specific components. The next talk in our series will be: Clifford Stein (Columbia Uni) | October 26 | Scheduling with Speed Predictions. 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

Alix Munier Kordon (Sorbonne U., LIP6) | September 28 | Synchronous DataFlow: A survival guide
by Zdeněk Hanzálek 26 Sep '22

26 Sep '22

Dear scheduling researcher, We are delighted to announce the talk given by Alix Munier Kordon (Sorbonne U., LIP6). The title is " Synchronous DataFlow: A survival guide ". The seminar will take place on Zoom on Wednesday, September 28 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95675289257?pwd=bnBHNWJrcmJPTytmMC9xbU5IQ2JXUT09 Meeting ID: 956 7528 9257 Passcode: 105839 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Synchronous Dataflow (SDF in short) were introduced in 1987 by Lee and Messerschmitt to model data exchanges in embedded systems. A SDF is usually defined by a directed graph, where each node is associated to a task that may be executed infinetly often. Each arc represents a buffer between two tasks. Moreover, the number of data samples produced or consumed by each task on each execution is specified a priori. Nowadays, SDF are considered by several scientific communities. It allows for example to model the exchanges for the design of Digital Signal Processings, or in real-time applications to run on a complex architecture. The purpose of this talk is to present a set of mathematical results developed on SDF, and to show how to use them to solve concrete problems posed by their users. We will also do the link with classical cyclic scheduling problems by demonstrating that the buffers can be associated to usual precedence constraints between successive task executions. We will conclude by some challenging open questions. The next talk in our series will be: Greet Vanden Berghe (KU Leuven) | October 12 | Vehicle routing - a focus on heuristic design. 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

Christos Zacharias (University of Miami) | September 14 | Dynamic Interday and Intraday Scheduling
by Zdeněk Hanzálek 12 Sep '22

12 Sep '22

Dear scheduling researcher, We are delighted to announce the talk given by Christos Zacharias (University of Miami). The title is "Dynamic Interday and Intraday Scheduling". The seminar will take place on Zoom on Wednesday, September 14 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95721352866?pwd=YXJ0bW9nN09XUldLbk1LbEo0YlN4Zz09 Meeting ID: 957 2135 2866 Passcode: 264401 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The simultaneous consideration of appointment day (interday scheduling) and time of day (intraday scheduling) in dynamic scheduling decisions is a theoretical and practical problem that has remained open. We introduce a novel dynamic programming framework that incorporates jointly these scheduling decisions in two timescales. Our model is designed with the intention of bridging the two streams of literature on interday and intraday scheduling and to leverage their latest theoretical developments in tackling the joint problem. We establish theoretical connections between two recent studies by proving novel theoretical results in discrete convex analysis regarding constrained multimodular function minimization. Grounded on our theory, we develop a practically implementable and computationally tractable scheduling paradigm with performance guarantees. Numerical experiments demonstrate that the optimality gap is less than 1% for practical instances of the problem. The next talk in our series will be: Alix Munier Kordon (Sorbonne U., LIP6) | September 28 | Synchronous DataFlow: A survival guide 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

Christos Zacharias (University of Miami) | September 14 | Dynamic Interday and Intraday Scheduling
by Zdeněk Hanzálek 07 Sep '22

07 Sep '22

Dear scheduling researcher, We are delighted to announce the talk given by Christos Zacharias (University of Miami). The title is "Dynamic Interday and Intraday Scheduling". The seminar will take place on Zoom on Wednesday, September 14 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95721352866?pwd=YXJ0bW9nN09XUldLbk1LbEo0YlN4Zz09 Meeting ID: 957 2135 2866 Passcode: 264401 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The simultaneous consideration of appointment day (interday scheduling) and time of day (intraday scheduling) in dynamic scheduling decisions is a theoretical and practical problem that has remained open. We introduce a novel dynamic programming framework that incorporates jointly these scheduling decisions in two timescales. Our model is designed with the intention of bridging the two streams of literature on interday and intraday scheduling and to leverage their latest theoretical developments in tackling the joint problem. We establish theoretical connections between two recent studies by proving novel theoretical results in discrete convex analysis regarding constrained multimodular function minimization. Grounded on our theory, we develop a practically implementable and computationally tractable scheduling paradigm with performance guarantees. Numerical experiments demonstrate that the optimality gap is less than 1% for practical instances of the problem. The next talk in our series will be: Alix Munier Kordon (Sorbonne U., LIP6) | September 28 | Synchronous DataFlow: A survival guide 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

[Scheduling seminar] Maurice Queyranne (Sauder School, UBC)| June 22 | On Polyhedral Approaches to Scheduling Problems
by Zdeněk Hanzálek 20 Jun '22

20 Jun '22

Dear scheduling researcher, We are delighted to announce the talk given by Maurice Queyranne (Sauder School, UBC). The title is "On Polyhedral Approaches to Scheduling Problems". The seminar will take place on Zoom on Wednesday, June 22 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91083429684?pwd=QlJXcHB4dGtLdE40b1hGaEVMbTNFdz09 Meeting ID: 910 8342 9684 Passcode: 190280 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The formulation of scheduling problems as mathematical optimization problems is a useful step in deriving exact solutions, or approximate solutions with performance guarantees. We give a brief overview of polyhedral approaches, which aim to apply the power of linear and mixed-integer optimization to certain classes of scheduling problems, in particular those with min-sum type of objectives such as to minimize weighted sums of completion dates. The choice of decision variables is the prime determinant of such formulations. Constraints, such as facet inducing inequalities for corresponding polyhedra, are often needed, in addition to those just required for the validity of the initial formulation, in order to derive useful dual bounds and structural insights. Alternative formulations are based on various types of decision variables, such as: start date and completion date variables, that simply specify when a task is performed; linear ordering variables, that prescribe the relative order of pairs of tasks; traveling salesman variables, which capture immediate succession of tasks and changeovers; assignment and positional date variables, which specify the assignment of tasks to machine or to positions; and time-indexed variables which rely on a discretization of the planning horizon, in particular machine switch-on and switch-off variables in production planning and unit commitment in power generation. We point out relationship between various models, and emphasize the role of supermodular polyhedra and greedy algorithms. The next talk in our series will be 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

Nicole Megow (Universität Bremen) | June 8 | Learning-Augmented Online Algorithms for Scheduling and Routing
by Zdeněk Hanzálek 06 Jun '22

06 Jun '22

Dear scheduling researcher, We are delighted to announce the talk given by Nicole Megow (Universität Bremen). The title is "Learning-Augmented Online Algorithms for Scheduling and Routing". The seminar will take place on Zoom on Wednesday, June 8 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/93281103550?pwd=ckU0dWRRYWFUb2tRV2duakRjMVgyZz09 Meeting ID: 932 8110 3550 Passcode: 197150 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Online optimization refers to solving problems where an initially unknown input is revealed incrementally, and irrevocable decisions must be made not knowing future requests. The assumption of not having any prior knowledge about future requests seems overly pessimistic. Given the success of machine-learning methods and data-driven applications, one may expect to have access to predictions about future requests. However, simply trusting them might lead to very poor solutions, as these predictions come with no quality guarantee. In this talk we present recent developments in the young line of research that integrates such error-prone predictions into algorithm design to break through worst case barriers. We discuss different prediction models and algorithmic challenges with a focus on online scheduling and routing and give an outlook to network design problems. The next talk in our series will be given by: Maurice Queyranne (Sauder School, UBC)| June 22 | On Polyhedral Approaches to 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

Stanislaw Gawiejnowicz (AMU Poznañ) | May 25 | Past, present and future of time-dependent scheduling
by Zdeněk Hanzálek 23 May '22

23 May '22

Dear scheduling researcher, We are delighted to announce the talk given by Stanislaw Gawiejnowicz (AMU Poznañ). The title is "Past, present and future of time-dependent scheduling". The seminar will take place on Zoom on Wednesday, May 25 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91521949771?pwd=a091cWhwY1RzUGdYck9QeFd3d29vQT09 Meeting ID: 915 2194 9771 Passcode: 759526 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. In the lecture, we will present a general landscape of time-dependent scheduling which is one of the main research domains in modern scheduling theory. This lecture will be divided into three parts. In the first part, we will sketch the main dates in time-dependent scheduling development, specify the most important forms of time-dependent processing times and formulate the basic assumptions of time-dependent scheduling. Next, we will present the main results from that area, paying a special attention to applied proof techniques and mutual relations between different time-dependent scheduling problems. Finally, we will discuss selected open problems in time-dependent scheduling, summarizing known results for each open problem and indicating possible ways of its further research. The next talk in our series will be given by: Nicole Megow (Universität Bremen) | June 8 | Scheduling under Uncertainty 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