Abstract : Scheduling theory has received a wide coverage in the literature on operations research and discrete optimization over the last five decades or so, but the literature seems to have reached a “sink” equilibrium with respect to the standard assumptions and parameters to be included in the models. In this symposium we aim to present recent new scheduling models that extend the classic ones, and where the extensions have a direct link with practical operations scheduling in a variety of industries. We focus especially also on computational methods for solving the new models.
[01483] Joint replenishment combined with machine scheduling: offline and online algorithms
Format : Talk at Waseda University
Author(s) :
Tamás Kis (SZTAKI)
Peter Gyorgyi (SZTAKI)
Timea Tamasi (SZTAKI)
Jozsef Bekesi (University of Szeged)
Abstract : In this scheduling problem, each job requires a subset of resource types that have to be purchased after the release date of the job and prior to starting the job. The goal is to determine a schedule along with the purchasing dates and quantities for each resource type to minimize the sum of purchasing costs plus a scheduling criterion.
Complexity results and online algorithms will be presented for different special cases of the problem.
[01552] Sequential testing in batches with resource constraints
Format : Talk at Waseda University
Author(s) :
Fan Yang (Shanghai Normal University)
Ben Hermans (ORTEC)
Nicolas ZUFFEREY (University of Geneva)
Roel Leus (KU Leuven)
Abstract : We consider the problem of determining the state of a system through costly tests of its components, where components can be tested simultaneously in batches to exploit economies of scale. This problem is a generalization of the classical sequential testing problem and it has applications in various settings, including machine maintenance, disease diagnosis, and new product development. We prove that the problem is strongly NP-hard, and several models and algorithms are proposed for it.
[00764] A flow-based formulation for parallel machine scheduling using decision diagrams
Format : Talk at Waseda University
Author(s) :
Daniel Kowalczyk (KU Leuven)
Roel Leus (KU Leuven)
Christopher Hojny (Eindhoven University of Technology)
Stefan Ropke (Technical University of Denmark)
Abstract : We present a new flow-based formulation for identical parallel machine scheduling, which is constructed with the help of a decision diagram that represents all job sequences that respect specific ordering rules. These rules rely on a partition of the planning horizon into, generally non-uniform, periods. We develop a branch-and-price framework that solves several instances from the literature for the first time. We compare the new formulation with the time-indexed and arc-time-indexed formulation.
[00808] Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms
Format : Online Talk on Zoom
Author(s) :
Guopeng Song (National University of Defense Technology)
Roel Leus (KU Leuven)
Abstract : We study parallel machine scheduling for makespan minimization with uncertain job processing times. To incorporate uncertainty and generate solutions that are insensitive to unfolding information, three different modeling paradigms are adopted: a robust model, a chance-constrained model, and a distributionally robust chance-constrained model. We focus on devising generic solution methods that can efficiently handle these different models. We compare the solutions from the different models for scheduling under uncertainty and report the general lessons learned.
[02307] Energy-aware flow shop scheduling with uncertain renewable energy
Format : Talk at Waseda University
Author(s) :
Morteza DAVARI (SKEMA Business School)
Masoumeh Ghorbanzadeh (Ferdowsi University)
Mohammad Ranjbar (Ferdowsi University)
Abstract : This paper investigates an energy-aware flow shop scheduling problem with on-site renewable and grid energy resources. To deal with the uncertainty of renewable energy resources, we first develop two two-stage stochastic programming formulations to minimize the total energy cost purchased from the grid and then, we develop two robust models. Computational results reveal that Benders decomposition algorithms outperform compact models for robust problems and not for stochastic problem.
[02657] An effective model-driven heuristic algorithm for the collaborative operating room scheduling problem
Format : Talk at Waseda University
Author(s) :
Yang Wang (School of Management, Northwestern Polytechnical University)
Haichao Liu (School of Management, Northwestern Polytechnical University)
Abraham Punnen (Simon Fraser University)
Abstract : In this work, we study a collaborative operating room scheduling problem subject to shared surgeons and
downstream wards. We propose an effective model-driven heuristic algorithm to make both weekly surgery assignment and daily sequencing decisions for multiple heterogeneous hospitals. Extensive experimental
results disclose the merit of the integrated optimization modelling and the usefulness of coordinating the
allocation of key resources within collaborative hospitals.
[01493] Valid inequalities for the parallel stack loading problem of minimizing the number of badly-placed items
Format : Talk at Waseda University
Author(s) :
Shunji Tanaka (Kyoto University)
Sven Boge (Osnabrück University)
Abstract : This study addresses the parallel stack loading problem to find an optimal loading plan of incoming items into parallel stacks so that the workload for retrieving them later is minimized. We propose valid inequalities for an integer programming formulation of the problem to minimize the number of badly-placed items as an index of the workload. We examine their effectiveness by computational experiment.
[01466] Branch-and-Price-and-Cut for the Team Orientation Problem with Interval-Time-Varying Profit
Format : Online Talk on Zoom
Author(s) :
jiaojiao li (National University of Defense Technology)
Abstract : This paper studies the team orienteering problem, where the profit depends on whether two visits are completed and the interval time of the two visits. The result of this interaction can be expressed as a discrete profit function. In the practical application of Earth observation satellites, it is often necessary to make two consecutive observations of some important targets at reasonable intervals to improve the observation effect. To solve the problem, we effectively describe the time interval requirement by the number of days between two visits and the combination of time windows, then formulate mixed-integer programming (MIP) models and propose a branch-and-price-cut algorithm, along with valid inequalities for tightening the upper bound. Computational results show the effectiveness of our algorithm. Furthermore, we analyze the impact of the following four aspects on computing time, including basic and modified graph, unidirectional and bidirectional label-setting, ng-path relaxation and dynamic ng-path relaxation, algorithms with and without the valid inequality. Then we present the impact of the third level of branching and non-branching on computing time and profit.
[03681] A hybrid algorithm of integrated container truck scheduling problem
Format : Talk at Waseda University
Author(s) :
Wenchao Wei
Yanrong Zhang (Beijing Jiaotong University)
Abstract : This article establishes an inland container transportation network that includes inland container depots (ICDs) and studies the dispatching problem of container empty containers and trucks in the network. A mixed integer programming model is proposed to tackle the scheduling problem together with ICD locations. To solve the proposed problem, we develop a hybrid algorithm combining large neighborhood search in a fix-and-optimize framework and a tabu search algorithm.
[05024] Compact formulations for parallel machine scheduling with conflicts
Format : Talk at Waseda University
Author(s) :
Phablo Moura (KU Leuven)
Roel Leus (KU Leuven)
Hande Yaman (KU Leuven)
Abstract : Parallel machine scheduling with conflicts consists in, given a set of jobs $V$ with known processing times, a set of identical machines $M$, and an undirected graph $(V,E)$, finding a mapping from $V$ to $M$ such that pairs of jobs in $E$ are assigned to different machines, and the maximum completion time (makespan) is minimized. We present compact MILP formulations, introduce classes of valid inequalities, and report on preliminary computational experiments
[01311] Project scheduling under various resource constraints
Format : Talk at Waseda University
Author(s) :
Nicklas Klein (University of Bern)
Mario Gnägi (University of Bern)
Norbert Trautmann (University of Bern)
Abstract : The execution of a project often requires two types of resources: renewable resources representing, e.g., staff members or equipment; and production and consumption resources representing, e.g., the project budget. We present a mixed-integer linear programming formulation for scheduling such a project which significantly outperforms state-of-the-art models from the literature.
