
Journal of Scheduling [SJR: 1.053] [HI: 47] [5 followers] Follow Hybrid journal (It can contain Open Access articles) ISSN (Print) 10991425  ISSN (Online) 10946136 Published by SpringerVerlag [2352 journals] 
 Journal of Scheduling (2018)
 Authors: Edmund Burke; Michael Pinedo
Pages: 1  1
PubDate: 20180201
DOI: 10.1007/s1095101805553
Issue No: Vol. 21, No. 1 (2018)
 Authors: Edmund Burke; Michael Pinedo
 A survey on how the structure of precedence constraints may change the
complexity class of scheduling problems Authors: D. Prot; O. BellenguezMorineau
Pages: 3  16
Abstract: This survey aims to demonstrate that the structure of precedence constraints plays a tremendous role on the complexity of scheduling problems. Indeed, many problems can be \(\mathcal {NP}\) hard when considering general precedence constraints, while they become polynomially solvable for particular precedence constraints. Additionally, the existence of many very exciting challenges in this research area is underlined.
PubDate: 20180201
DOI: 10.1007/s109510170519z
Issue No: Vol. 21, No. 1 (2018)
 Authors: D. Prot; O. BellenguezMorineau
 Case mix classification and a benchmark set for surgery scheduling
 Authors: Gréanne Leeftink; Erwin W. Hans
Pages: 17  33
Abstract: Numerous benchmark sets exist for combinatorial optimization problems. However, in healthcare scheduling, only a few benchmark sets are known, mainly focused on nurse rostering. One of the most studied topics in the healthcare scheduling literature is surgery scheduling, for which there is no widely used benchmark set. An effective benchmark set should be diverse, reflect the real world, contain large instances, and be extendable. This paper proposes a benchmark set for surgery scheduling algorithms, which satisfies these four criteria. Surgery scheduling instances are characterized by an underlying case mix, which describes the volume and properties of the surgery types. Given a case mix, unlimited random instances can be generated. A complete surgery scheduling benchmark set should encompass the diversity of prevalent case mixes. We therefore propose a case mix classification scheme, which we use to typify both reallife and theoretical case mixes that span the breadth of possible case mix types. Our full benchmark set contains 20,880 instances, with a small benchmark subset of 146 instances. The instances are generated based on reallife case mixes (11 surgical specialties), as well as theoretical instances. The instances were generated using a novel instance generation procedure, which introduces the concept of “instance proximity” to measure the similarity between two instances, and which uses this concept to generate sets of instances that are as diverse as possible.
PubDate: 20180201
DOI: 10.1007/s1095101705398
Issue No: Vol. 21, No. 1 (2018)
 Authors: Gréanne Leeftink; Erwin W. Hans
 Energyefficient scheduling and routing via randomized rounding
 Authors: Evripidis Bampis; Alexander Kononov; Dimitrios Letsios; Giorgio Lucarelli; Maxim Sviridenko
Pages: 35  51
Abstract: We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speedscaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptivenonmigratory and the preemptivemigratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptivenonmigratory variant, we are able to improve the best known approximation ratio for the single processor nonpreemptive problem. Furthermore, we show that our approach allows to obtain a constantfactor approximation algorithm for the poweraware preemptive job shop scheduling problem. Finally, we consider the minpower routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
PubDate: 20180201
DOI: 10.1007/s1095101605002
Issue No: Vol. 21, No. 1 (2018)
 Authors: Evripidis Bampis; Alexander Kononov; Dimitrios Letsios; Giorgio Lucarelli; Maxim Sviridenko
 Solving a wind turbine maintenance scheduling problem
 Authors: Aurélien Froger; Michel Gendreau; Jorge E. Mendoza; Eric Pinson; LouisMartin Rousseau
Pages: 53  76
Abstract: Driven by climate change mitigation efforts, the wind energy industry has significantly increased in recent years. In this context, it is essential to make its exploitation costeffective. Maintenance of wind turbines therefore plays an essential role in reducing breakdowns and ensuring high productivity levels. In this paper, we discuss a challenging maintenance scheduling problem rising in the onshore wind power industry. While the research in the field primarily focuses on conditionbased maintenance strategies, we aim to address the problem on a shortterm horizon considering the wind speed forecast and a finegrained resource management. The objective is to find a maintenance plan that maximizes the revenue from the electricity production of the turbines while taking into account multiple task execution modes and tasktechnician assignment constraints. To solve this problem, we propose a constraint programmingbased large neighborhood search (CPLNS) approach. We also propose two integer linear programming formulations that we solve using a commercial solver. We report results on randomly generated instances built with input from wind forecasting and maintenance scheduling software companies. The CPLNS shows an average gap of 1.2% with respect to the optimal solutions if known, or to the best upper bounds otherwise. These computational results demonstrate the overall efficiency of the proposed metaheuristic.
PubDate: 20180201
DOI: 10.1007/s1095101705135
Issue No: Vol. 21, No. 1 (2018)
 Authors: Aurélien Froger; Michel Gendreau; Jorge E. Mendoza; Eric Pinson; LouisMartin Rousseau
 Scheduling shared continuous resources on manycores
 Authors: Ernst Althaus; André Brinkmann; Peter Kling; Friedhelm Meyer auf der Heide; Lars Nagel; Sören Riechers; Jiří Sgall; Tim Süß
Pages: 77  92
Abstract: We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement . The job can be processed at full speed if granted its full resource requirement. If receiving only an xportion of \(r_j\) , it is processed at an xfraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete–continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this article, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NPhard if the number of processors is part of the input. Positive results for unit size jobs include a polynomialtime algorithm for any constant number of processors. Since the running time is infeasible for practical purposes, we also provide more efficient algorithm variants: an optimal algorithm for two processors and a approximation algorithm for m processors.
PubDate: 20180201
DOI: 10.1007/s1095101705180
Issue No: Vol. 21, No. 1 (2018)
 Authors: Ernst Althaus; André Brinkmann; Peter Kling; Friedhelm Meyer auf der Heide; Lars Nagel; Sören Riechers; Jiří Sgall; Tim Süß
 Task assignment with start timedependent processing times for personnel
at checkin counters Authors: Emilio Zamorano; Annika Becker; Raik Stolletz
Pages: 93  109
Abstract: This paper addresses a task assignment problem encountered by checkin counter personnel at airports. The problem consists of assigning multiskilled agents to a sequence of tasks in checkin counters. Because each task’s ending time is fixed to comply with the flight schedule, its processing time depends on the arrival of the assigned agents. We propose a mixedinteger program and a branchandprice algorithm to solve this problem. We exploit the problem structure to efficiently formulate the pricing problems and improve computation time. Using realworld data from a German groundhandling agency, we conduct numerical studies to evaluate the performance of the proposed solutions.
PubDate: 20180201
DOI: 10.1007/s1095101705233
Issue No: Vol. 21, No. 1 (2018)
 Authors: Emilio Zamorano; Annika Becker; Raik Stolletz
 Scheduling electric vehicles and locating charging stations on a path
 Authors: Nils Boysen; Dirk Briskorn; Simon Emde
Pages: 111  126
Abstract: High hopes are put in electric vehicles to lower global green house gas emissions. From an operational perspective, however, their limited range and the long recharging times add considerable complexity to the decision tasks planning their efficient application. In this context, we treat a problem setting where a single electric vehicle executes transport requests along a straight line, which, for instance, occurs when cranes, automated guided vehicles, or shuttles handle boxes in container terminals. From time to time the vehicle needs to be recharged and, thus, has to visit some charging station also located on the line. We investigate the scheduling of a single electric vehicle, so that the makespan for executing all transport requests is minimized and the vehicle is timely recharged. The solution algorithm developed is then applied to also explore the location planning of charging stations.
PubDate: 20180201
DOI: 10.1007/s1095101705389
Issue No: Vol. 21, No. 1 (2018)
 Authors: Nils Boysen; Dirk Briskorn; Simon Emde
 Combining twostage stochastic programming and recoverable robustness to
minimize the number of late jobs in the case of uncertain processing times
 Authors: Marjan van den Akker; Han Hoogeveen; Judith Stoef
Abstract: Minimizing the number of late jobs on a single machine is a classic scheduling problem, which can be used to model the situation that from a set of potential customers, we have to select as many as possible whom we want to serve, while selling no to the other ones. This problem can be solved by Moore–Hodgson’s algorithm, provided that all data are deterministic. We consider a stochastic variant of this problem, where we assume that there is a small probability that the processing times differ from their standard values as a result of some kind of disturbance. When such a disturbance occurs, then we must apply some recovery action to make the solution feasible again. This leads us to the area of recoverable robustness, which handles this uncertainty by modeling each possible disturbance as a scenario; in each scenario, the initial solution must then be made feasible by applying a given, simple recovery algorithm to it. Since we cannot accept previously rejected customers, our only option is to reject customers that would have been served in the undisturbed case. Our problem therefore becomes to find a solution for the undisturbed case together with a feasible recovery to every possible disturbance. Our goal hereby is to maximize the expected number of served customers; we assume here that we know the probability that a given scenario occurs. In this respect, our problem falls outside the area of the ‘standard’ recoverable robustness, which contains the worstcase recovery cost as a component of the objective. Therefore, we consider our approach as a combination of twostage stochastic programming and recoverable robustness. We show that this problem is \(\mathcal{NP}\) hard in the ordinary sense even if there is only one scenario, and we present some sufficient conditions that allow us to find a part of the optimal solution in polynomial time. We further evaluate several solution methods to find an optimal solution, among which are dynamic programming, branchandbound, and branchandprice.
PubDate: 20180219
DOI: 10.1007/s109510180559z
 Authors: Marjan van den Akker; Han Hoogeveen; Judith Stoef
 An efficient train scheduling algorithm on a singletrack railway system
 Authors: Xiaoming Xu; Keping Li; Lixing Yang; Ziyou Gao
Abstract: Since scheduling trains on a singletrack railway line is an NPhard problem, this paper proposes an efficient heuristic algorithm based on a train movement simulation method to search for the nearoptimal train timetables within the acceptable computational time. Specifically, the time–space statuses of trains in the railway system are firstly divided into three categories, including dwelling at a station, waiting at a station and traveling on a segment. A check algorithm is particularly proposed to guarantee the feasibility of transition among different statuses in which each status transition is defined as a discrete event. Several detailed operation rules are also developed to clarify the scheduling procedure in some special cases. We then design an iterative discrete event simulationbased train scheduling method, namely, train status transition approach (TSTA), in which the status transition check algorithm and operation rules are incorporated. Finally, we implement some extensive experiments by using randomly generated data set to show the effectiveness and efficiency of the proposed TSTA.
PubDate: 20180217
DOI: 10.1007/s1095101805580
 Authors: Xiaoming Xu; Keping Li; Lixing Yang; Ziyou Gao
 Online scheduling of moldable parallel tasks
 Authors: Deshi Ye; Danny Z. Chen; Guochuan Zhang
Abstract: In this paper, we study an online scheduling problem with moldable parallel tasks on m processors. Each moldable task can be processed simultaneously on any number of processors of a parallel computer, and the processing time of a moldable task depends on the number of processors allotted to it. Tasks arrive one by one. Upon arrival of each task, the scheduler has to determine both the number of processors and the starting time for the task. Moreover, these decisions cannot be changed in the future. The objective is to attain a schedule such that the longest completion time over all tasks, i.e., the makespan, is minimized. First, we provide a general framework to show that any \(\rho \) bounded algorithm for scheduling of rigid parallel tasks (the number of processors for a task is fixed a prior) can be extended to yield an algorithm for scheduling of moldable tasks with a competitive ratio of \(4\rho \) if the ratio \(\rho \) is known beforehand. As a consequence, we achieve the first constant competitive ratio, 26.65, for the moldable parallel tasks scheduling problem. Next, we provide an improved algorithm with a competitive ratio of at most 16.74.
PubDate: 20180202
DOI: 10.1007/s1095101805562
 Authors: Deshi Ye; Danny Z. Chen; Guochuan Zhang
 A twostage stochastic program for multishift, multianalyst, workforce
optimization with multiple oncall options Authors: Douglas S. Altner; Anthony C. Rojas; Leslie D. Servi
Abstract: Motivated by a cybersecurity workforce optimization problem, this paper investigates optimizing staffing and shift scheduling decisions given unknown demand and multiple oncall staffing options at a 24/7 firm with three shifts per day, three analyst types, and several staffing and scheduling constraints. We model this problem as a twostage stochastic program and solve it with a columngenerationbased heuristic. Our computational study shows this method only needs 3 min to produce solutions within 6% of a true lower bound of the optimal for 99% of over 150 test cases.
PubDate: 20171222
DOI: 10.1007/s1095101705549
 Authors: Douglas S. Altner; Anthony C. Rojas; Leslie D. Servi
 A unified heuristic and an annotated bibliography for a large class of
earliness–tardiness scheduling problems Authors: Arthur Kramer; Anand Subramanian
Abstract: This work proposes a unified heuristic algorithm for a large class of earliness–tardiness (E–T) scheduling problems. We consider single/parallel machine E–T problems that may or may not consider some additional features such as idle time, setup times and release dates. In addition, we also consider those problems whose objective is to minimize either the total (average) weighted completion time or the total (average) weighted flow time, which arise as particular cases when the due dates of all jobs are either set to zero or to their associated release dates, respectively. The developed local searchbased metaheuristic framework is quite simple, but at the same time relies on sophisticated procedures for efficiently performing local search according to the characteristics of the problem. We present efficient move evaluation approaches for some parallel machine problems that generalize the existing ones for single machine problems. The algorithm was tested in thousands of instances of several E–T problems and particular cases. The results obtained show that our unified heuristic is capable of producing highquality solutions when compared to the best ones available in the literature that were obtained by specific methods. Moreover, we provide an extensive annotated bibliography on the problems related to those considered in this work, where we not only indicate the approach(es) used in each publication, but we also point out the characteristics of the problem(s) considered. Beyond that, we classify the existing methods in different categories so as to have a better idea of the popularity of each type of solution procedure.
PubDate: 20171215
DOI: 10.1007/s1095101705496
 Authors: Arthur Kramer; Anand Subramanian
 The proactive and reactive resourceconstrained project scheduling problem
 Authors: Morteza Davari; Erik Demeulemeester
Abstract: Uncertainty has become an inevitable aspect of project scheduling. We study the resourceconstrained project scheduling problem with stochastic durations. One of the most studied approaches to deal with stochastic durations is that of proactive and reactive scheduling. Previous researches often studied proactive and reactive scheduling rather separately and ignored the fact that proactive scheduling and reactive scheduling are closely connected. In this paper, we address this ignored aspect by formulating an integrated proactive and reactive scheduling problem with a combined cost function which includes a baseline schedule cost as well as costs of a series of reactions. We introduce solutions to this integrated problem as proactiveandreactive policies (PRpolicies). We discuss that PRpolicies are more powerful and informative than their traditional counterparts (i.e., a combination of a baseline schedule and a reactive policy), provide better stability and robustness, and are more flexible when extra constraints are added to the problem. We also propose four dynamic programming based models (Models 1–4) that solve the problem to optimality over different classes of PRpolicies. We compare our models with each other and with a combination of a traditional proactive approach (namely, the starting time criticality heuristic) and a reactive approach (namely, the robust parallel schedule generation scheme). Computational results show that Model 2 outperforms the traditional solution only when reaction costs are greater than zero. Moreover, Model 3 and Model 4 clearly outperform Model 1 and Model 2 in all settings and the traditional solution in most of the settings.
PubDate: 20171213
DOI: 10.1007/s109510170553x
 Authors: Morteza Davari; Erik Demeulemeester
 Models and algorithms for energyefficient scheduling with immediate start
of jobs Authors: Akiyoshi Shioura; Natalia V. Shakhlevich; Vitaly A. Strusevich; Bernhard Primas
Abstract: We study a scheduling model with speed scaling for machines and the immediate start requirement for jobs. Speed scaling improves the system performance, but incurs the energy cost. The immediate start condition implies that each job should be started exactly at its release time. Such a condition is typical for modern Cloud computing systems with abundant resources. We consider two cost functions, one that represents the quality of service and the other that corresponds to the cost of running. We demonstrate that the basic scheduling model to minimize the aggregated cost function with n jobs is solvable in \(O(n\log n)\) time in the singlemachine case and in \(O(n^{2}m)\) time in the case of m parallel machines. We also address additional features, e.g., the cost of job rejection or the cost of initiating a machine. In the case of a single machine, we present algorithms for minimizing one of the cost functions subject to an upper bound on the value of the other, as well as for finding a Paretooptimal solution.
PubDate: 20171212
DOI: 10.1007/s109510170552y
 Authors: Akiyoshi Shioura; Natalia V. Shakhlevich; Vitaly A. Strusevich; Bernhard Primas
 Parallel machine makespan minimization subject to machine availability and
total completion time constraints Authors: Yumei Huo
Abstract: In this paper, we study the parallel machine scheduling subject to machine availability constraint. The jobs can be resumed after being preempted by another job or interrupted by the unavailable intervals. The goal is to minimize the makespan subject to the constraint that the total completion time is minimized. We study two different machine unavailability models. In the first model, each machine has a single unavailable interval which starts from time 0. In the second model, each machine can have multiple unavailable intervals, but at any time, there is at most one machine unavailable. For each model, we show that there is an optimal polynomial time algorithm.
PubDate: 20171211
DOI: 10.1007/s109510170551z
 Authors: Yumei Huo
 Special issue: Twelfth Workshop on Models and Algorithms for Planning and
Scheduling Problems (MAPSP 2015) Authors: Yves Crama; Dries Goossens; Roel Leus; Michaël Schyns; Frits Spieksma
PubDate: 20171110
DOI: 10.1007/s1095101705487
 Authors: Yves Crama; Dries Goossens; Roel Leus; Michaël Schyns; Frits Spieksma
 The Current state of bounds on benchmark instances of the jobshop
scheduling problem Authors: Jelke J. van Hoorn
Abstract: Scheduling problems have received considerable attention over the last decade. Several sets of benchmark instances are available for comparing the quality of the different methods developed. A large number of publications achieve either the current best known or improved bounds for a subset of these instances. It is unfortunate, however, that several publications erroneously reference the current state of these bounds. This article aims to provide an accurate overview of the current state of the bounds for eight sets of benchmark instances. In addition to careful reading of the references cited, in some instances the authors were contacted directly to verify these bounds. This was necessary when the bounds were not reported in the referenced work, or when the work was unavailable to me. The article also includes a brief overview of the techniques that were used to obtain these bounds.
PubDate: 20171028
DOI: 10.1007/s1095101705478
 Authors: Jelke J. van Hoorn
 Complexity results for an integrated single machine scheduling and
outbound delivery problem with fixed sequence Abstract: In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine, and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time, and transportation times between customers are taken into account. Because the sequence is given, the problem consists in forming batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NPhardness of the general problem is established, and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NPhardness proofs and polynomial time algorithms are given. Finally, a fixedparameter tractability result is given.
PubDate: 20170908
DOI: 10.1007/s1095101705402
 Abstract: In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine, and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time, and transportation times between customers are taken into account. Because the sequence is given, the problem consists in forming batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NPhardness of the general problem is established, and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NPhardness proofs and polynomial time algorithms are given. Finally, a fixedparameter tractability result is given.