Skip to main content

Journal of Scheduling OnlineFirst articles

13.07.2020 Open Access

New results for an open time-dependent scheduling problem

We present several new results for a single machine time-dependent scheduling problem of minimizing the total completion time of a set of linearly deteriorating jobs with unit basic processing times. First, we show new properties of cyclic …

Stanisław Gawiejnowicz, Wiesław Kurc


Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty

Quay crane scheduling is a key aspect of container terminal operation, which can be regarded as a decision-making process with uncertainty. Each task involves stochastic loading and unloading operation times owing to the existence of uncertainty.

Shoufeng Ma, Hongming Li, Ning Zhu, Chenyi Fu


Dynamic speed scaling minimizing expected energy consumption for real-time tasks

This paper proposes a discrete time Markov decision process approach to compute the optimal on-line speed scaling policy to minimize the energy consumption of a single processor executing a finite or infinite set of jobs with real-time …

Bruno Gaujal, Alain Girault, Stephan Plassart

30.06.2020 Open Access

A decomposition heuristic for rotational workforce scheduling

In rotational workforce planning, a schedule is constructed from a sequence of work and rest periods. Each employee starts at a different part of the schedule, and after a certain amount of time, the schedule repeats. The length of the schedule …

Tristan Becker


A periodic optimization approach to dynamic pickup and delivery problems with time windows

In dynamic pickup and delivery problems with time windows (PDPTWs), potentially urgent request information is released over time. This gradual data availability means the decision-making process must be continuously repeated. These decisions are …

Farzaneh Karami, Wim Vancroonenburg, Greet Vanden Berghe


Scheduling two projects with controllable processing times in a single-machine environment

We consider two single-machine scheduling problems in which two competing projects share one common resource. Each project has multiple interim assessments, and its own jobs are ordered completely. A tardy job incurs a tardiness penalty cost which …

Byung-Cheon Choi, Myoung-Ju Park


Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection

In this paper we study a single batch-processing machine scheduling model. In our model, a set of jobs having different release dates needs to be scheduled onto a single machine that can process a batch of jobs simultaneously at a time. Each batch …

Jinwen Ou


An integrated rolling horizon approach to increase operating theatre efficiency

Demand for healthcare is increasing rapidly. To meet demand, we must improve the efficiency of our public health services. We present a mixed integer programming formulation that simultaneously tackles the integrated master surgical schedule and …

Belinda Spratt, Erhan Kozan


Serial-batching scheduling with two agents to minimize makespan and maximum cost

This paper considers three serial-batching scheduling problems with two agents to minimize the makespan of agent A and maximum cost (or maximum lateness) of agent B simultaneously. In these two-agent scheduling problems, jobs of different agents …

Cheng He, Chunqi Xu, Hao Lin

20.05.2020 Open Access

An approach to reduce energy consumption and performance losses on heterogeneous servers using power capping

Rapid growth of demand for remote computational power, along with high energy costs and infrastructure limits, has led to treating power usage as a primary constraint in data centers. Especially, recent challenges related to development of …

Tomasz Ciesielczyk, Alberto Cabrera, Ariel Oleksiak, Wojciech Piątek, Grzegorz Waligóra, Francisco Almeida, Vicente Blanco


Approximation algorithms for energy-efficient scheduling of parallel jobs

In this paper, we consider the homogeneous scheduling on speed-scalable processors, where the energy consumption is minimized. While most previous works have studied single-processor jobs, we focus on rigid parallel jobs, using more than one …

Alexander Kononov, Yulia Kovalenko

21.02.2020 Open Access

Cyclic lot-sizing problems with sequencing costs

We study a single-machine lot-sizing problem, where n types of products need to be scheduled on the machine. Each product is associated with a constant demand rate, maximum production rate and inventory costs per time unit. Every time when the …

Alexander Grigoriev, Vincent J. Kreuzen, Tim Oosterwijk

20.02.2020 Open Access

Scheduling in data gathering networks with background communications

In this work, we study scheduling in star data gathering networks with background communications. The worker nodes of the network hold datasets that have to be transferred directly to the base station. The communication speed of each link changes …

Joanna Berlińska


Measuring the complexity of university timetabling instances

University timetabling is a real-world problem frequently encountered in higher education institutions. It has been studied by many researchers who have proposed a wide variety of solutions. Measuring the variation of the performance of solution …

Felipe de la Rosa-Rivera, Jose I. Nunez-Varela, Cesar A. Puente-Montejano, Sandra E. Nava-Muñoz


Mirror scheduling problems with early work and late work criteria

We give a definition of a class of mirror scheduling problems, review existing representatives of this class and demonstrate that an identical parallel machine scheduling problem with precedence constraints and an upper bound on the makespan to …

Xin Chen, Sergey Kovalev, Małgorzata Sterna, Jacek Błażewicz


Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments

We study a scheduling environment that finds many real-world manufacturing applications, in which there is a close connection between a hybrid multiprocessor open shop and multiple parallel identical flow shops. In this environment, there is an …

Jianming Dong, Joshua Chang, Bing Su, Jueliang Hu, Guohui Lin

20.11.2019 Open Access

Scheduling divisible loads with time and cost constraints

In distributed computing, divisible load theory provides an important system model for allocation of data-intensive computations to processing units working in parallel. The main task is to define how a computation job should be split into parts …

M. Drozdowski, N. V. Shakhlevich

02.11.2019 Open Access

Refined conditions for V-shaped optimal sequencing on a single machine to minimize total completion time under combined effects

We address single-machine scheduling problems for which the actual processing times of jobs are subject to various effects, including a positional effect, a cumulative effect and their combination. We review the known results on the problems to …

Alan J. Soper, Vitaly A. Strusevich


Less is more: variable neighborhood search for integrated production and assembly in smart manufacturing

This paper investigates an integrated production and assembly scheduling problem with the practical manufacturing features of serial batching and the effects of deteriorating and learning. The problem is divided into two stages. During the …

Shaojun Lu, Jun Pei, Xinbao Liu, Xiaofei Qian, Nenad Mladenovic, Panos M. Pardalos


A technical note: fully polynomial time approximation schemes for minimizing the makespan of deteriorating jobs with nonlinear processing times

Fully polynomial time approximation schemes for scheduling deteriorating jobs with nonlinear processing times on a single machine are given via an application of the K-approximation sets and functions technique.

Nir Halman