A survey on makespan minimization in semi-online environments
We discuss variants of online scheduling on identical and uniformly related machines, where the objective is to minimize the makespan. All variants are such that some information regarding the input is provided in advance, and therefore these models are ...
An implicit model for multi-activity shift scheduling problems
We consider a multi-activity shift scheduling problem where the objective is to construct anonymous multi-activity shifts that respect union rules, satisfy the demand and minimize workforce costs. An implicit approach using adapted forward and backward ...
The triangle scheduling problem
- Christoph Dürr,
- Zdenĕk Hanzálek,
- Christian Konrad,
- Yasmina Seddik,
- René Sitters,
- Óscar C. Vásquez,
- Gerhard Woeginger
This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown ...
Improved algorithms for resource allocation under varying capacity
We consider the problem of scheduling a set of jobs on a system that offers certain resource, wherein the amount of resource offered varies over time. For each job, the input specifies a set of possible scheduling instances, where each instance is given ...
Flexible bandwidth assignment with application to optical networks
We introduce two scheduling problems, the flexible bandwidth allocation problem ($$\textsc {FBAP}$$FBAP) and the flexible storage allocation problem ($$\textsc {FSAP}$$FSAP). In both problems, we have an available resource, and a set of requests, each ...
Single machine scheduling with job delivery to multiple customers
We investigate a single machine scheduling problem with job delivery to multiple customers. In this problem, each job needs to be processed on the single machine, and then delivered by a single vehicle to its customer, where the job has a physical size ...
New strategies for stochastic resource-constrained project scheduling
We study the stochastic resource-constrained project scheduling problem or SRCPSP, where project activities have stochastic durations. A solution is a scheduling policy, and we propose a new class of policies that is a generalization of most of the ...
Algorithms for a special class of state-dependent shortest path problems with an application to the train routing problem
We study the state-dependent shortest path problem and focus on its application to the Single Train Routing Problem consisting of a rail network with only double-track segments, where the objective is to route one train through an empty network as fast ...