
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 [2335 journals] 
 Increasing airport capacity utilisation through optimum slot scheduling:
review of current developments and identification of future needs Authors: Konstantinos G. Zografos; Michael A. Madas; Konstantinos N. Androutsopoulos
Pages: 3  24
Abstract: Most of the busiest airports worldwide experience serious congestion and delay problems which call for some immediate capacity and demand management action. Solutions aiming to manage congestion through better slot scheduling have lately received a great deal of consideration due to their potential for delivering quick and substantial capacity utilisation improvements. A slot scheduling approach brings promises to cope better with congestion problems in the short to medium run and in a more sustainable way based on existing resources. This paper aims to provide a critical review of current research in declared capacity modelling and strategic slot scheduling. Furthermore, it goes beyond the critical review of current research developments by identifying future research issues and gaps and developing concrete directions towards modelling and solving advanced single airport and networkbased slot scheduling problems. Our research findings suggest that the next generation of slot scheduling models should explore variations of currently used objectives (e.g., alternative expressions of schedule delay) and most importantly enrich them with fairness and equity, resource utilisation and environmental considerations. Future modelling efforts should also aim to further investigate airlines’ utility of alternative slot allocation outcomes, including various acceptability measures and levels of tolerance against schedule displacements. Last but not least, future research should intensively focus on the development and validation of computationally viable and robust slot scheduling models being able to capture the complexity, dynamic nature and weatherinduced uncertainty of airport operations, along with hybrid solution approaches being able to deal with the size and complexity of slot allocation at network level.
PubDate: 20170201
DOI: 10.1007/s1095101604967
Issue No: Vol. 20, No. 1 (2017)
 Authors: Konstantinos G. Zografos; Michael A. Madas; Konstantinos N. Androutsopoulos
 Optimizing railway crew schedules with fairness preferences
 Authors: Silke Jütte; Daniel Müller; Ulrich W. Thonemann
Pages: 43  55
Abstract: Railway crew scheduling deals with generating duties for train drivers to cover all train movements of a given timetable while taking into account a set of work regulations. The objective is to minimize the overall costs associated with a crew schedule, which includes workforce costs and hotel costs. A cost minimal schedule often contains duties that are unpopular to train drivers, and these unpopular duties are often unevenly distributed among crew depots. At the company that motivated our research, for example, train drivers dislike duties that start in the early morning hours. Currently, some crew depots operate large numbers of these unpopular duties, while others do not have any unpopular duties at all. The train drivers perceive this situation as unfair. They prefer schedules with fewer and more evenly distributed unpopular duties across crew depots. In this paper, we define and measure unpopularity and (un)fairness in a railway crew scheduling context. We integrate fairness conditions into a column generationbased solution algorithm and analyze the effect of increased fairness on cost. We also show how increased fairness affects the unpopularity of a schedule. Our method has been applied to test instances at a large European railway freight carrier. Compared to a standard approach that penalizes only the number of unpopular duties in a schedule, we were able to significantly improve schedule fairness with only marginal increases in schedule cost.
PubDate: 20170201
DOI: 10.1007/s1095101604994
Issue No: Vol. 20, No. 1 (2017)
 Authors: Silke Jütte; Daniel Müller; Ulrich W. Thonemann
 An integrated model for the transshipment yard scheduling problem
 Authors: Mateusz Cichenski; Florian Jaehn; Grzegorz Pawlak; Erwin Pesch; Gaurav Singh; Jacek Blazewicz
Pages: 57  65
Abstract: A hubandspoke railway system is an efficient way of handling freight transport by land. A modern rail–rail train yard consists of huge gantry cranes that move the containers between the trains. In this context, we consider a rail–rail transshipment yard scheduling problem (TYSP) where the containers arrive to the hub and need to be placed on a train that will deliver them to their destination. In the literature, the problem is decomposed hierarchically into five subproblems, which are solved separately. First, the trains have to be grouped into bundles in which they visit the yard. Next, the trains have to be assigned to tracks within these bundles, namely parking positions. Then the final positions for the containers on trains have to be determined. Next, the container moves that need to be performed are assigned to the cranes. Finally, these moves have to be sequenced for each crane for processing. In this paper, an integrated MILP model is proposed, which aims to solve the TYSP as a single optimization problem. The proposed formulation also enables us to define more robust and complex objective functions that include key characteristics from each of the abovementioned subproblems. The strength of our proposed formulation is demonstrated via computational experiments using the data from the literature. Indeed, the results show that the TYSP can be solved without the use of decomposition techniques and more insight can be obtained from the same input data used to solve particular single decomposed subproblems.
PubDate: 20170201
DOI: 10.1007/s1095101604704
Issue No: Vol. 20, No. 1 (2017)
 Authors: Mateusz Cichenski; Florian Jaehn; Grzegorz Pawlak; Erwin Pesch; Gaurav Singh; Jacek Blazewicz
 Realtime management of berth allocation with stochastic arrival and
handling times Authors: Nitish Umang; Michel Bierlaire; Alan L. Erera
Pages: 67  83
Abstract: In this research we study the berth allocation problem (BAP) in real time as disruptions occur. In practice, the actual arrival times and handling times of the vessels deviate from their expected or estimated values, which can disrupt the original berthing plan and possibly make it infeasible. We consider a given baseline berthing schedule, and solve the BAP on a rolling planning horizon with the objective to minimize the total realized cost of the updated berthing schedule, as the actual arrival and handling time data is revealed in real time. The uncertainty in the data is modeled by making appropriate assumptions about the probability distributions of the uncertain parameters based on past data. We present an optimizationbased recovery algorithm based on set partitioning and a smart greedy algorithm to reassign vessels in the event of disruption. Our research problem derives from the realworld issues faced by the Saqr port, Ras Al Khaimah, UAE, where the berthing plans are regularly disrupted owing to a high degree of uncertainty in information. A simulation study is carried out to assess the solution performance and efficiency of the proposed algorithms, in which the baseline schedule is the solution of the deterministic BAP without accounting for any uncertainty. Results indicate that the proposed reactive approaches can significantly reduce the total realized cost of berthing the vessels as compared to the ongoing practice at the port.
PubDate: 20170201
DOI: 10.1007/s1095101604802
Issue No: Vol. 20, No. 1 (2017)
 Authors: Nitish Umang; Michel Bierlaire; Alan L. Erera
 Scheduling reclaimers serving a stock pad at a coal terminal
 Authors: Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
Pages: 85  101
Abstract: We study a variant of an abstract scheduling problem inspired by the management of reclaimers in the stockyard of a coal export terminal. We prove NPcompleteness of the problem and formulate it as a mixedinteger program. We show that for a given reclaiming sequence, the problem can be solved in pseudopolynomial time. In addition, we provide simple, constantfactor approximation algorithms as well as exact branchandbound algorithms. An extensive computational study analyzes the performance of the algorithms.
PubDate: 20170201
DOI: 10.1007/s1095101604958
Issue No: Vol. 20, No. 1 (2017)
 Authors: Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
 Optimizationbased resource allocation for software as a service
application in cloud computing Authors: Chunlin Li; Yun Chang Liu; Xin Yan
Pages: 103  113
Abstract: Software as a service (SaaS) is a software that is developed and hosted by the SaaS vendor. SaaS cloud provides software as services to the users through the internet. To provide good quality of service for the user, the SaaS relies on the resources leased from infrastructure as a service cloud providers. As the SaaS services rapidly expand their application scopes, it is important to optimize resource allocation in SaaS cloud. The paper presents optimizationbased resource allocation approach for software as a service application in cloud. The paper uses optimization decomposition approach to solve cloud resource allocation for satisfying the cloud user’s needs and the profits of the cloud providers. The paper also proposes a SaaS cloud resource allocation algorithm. The experiments are designed to compare the performance of the proposed algorithm with other two related algorithms.
PubDate: 20170201
DOI: 10.1007/s109510160491z
Issue No: Vol. 20, No. 1 (2017)
 Authors: Chunlin Li; Yun Chang Liu; Xin Yan
 Solving a wind turbine maintenance scheduling problem
 Authors: Aurélien Froger; Michel Gendreau; Jorge E. Mendoza; Eric Pinson; LouisMartin Rousseau
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: 20170317
DOI: 10.1007/s1095101705135
 Authors: Aurélien Froger; Michel Gendreau; Jorge E. Mendoza; Eric Pinson; LouisMartin Rousseau
 The impact of overtime as a timebased proactive scheduling and reactive
allocation strategy on the robustness of a personnel shift roster Authors: Jonas Ingels; Broos Maenhout
Abstract: The workforce size and the overtime budget have an important impact on the total personnel costs of an organisation. Since the personnel costs represent a significant fraction of the operating costs, it is important to define an appropriate hiring and overtime policy. Overtime is defined as an extension of the daily working time or the total working time over the planning period. In this paper, we make the distinction between scheduled and unscheduled overtime when we define the overtime policy. Scheduled overtime is proactively assigned in the baseline personnel roster whereas unscheduled overtime is allocated as a reactive strategy to overcome operational disruptions. The hiring and overtime policy undoubtedly influence the robustness included in a personnel roster, i.e., the capability of an organisation to deal with roster disruptions at an acceptable cost. In this paper, we investigate the tradeoff between the hiring budget and the overtime budget and the way overtime should be allocated in the personnel management process. The latter comprehends a tradeoff between the proactive scheduling of overtime and the reservation of overtime to balance supply and demand in response to operational variability. Insights are obtained by exploring three different strategies to compose a personnel shift baseline roster. We verify the robustness of each of these strategies by applying a threestep methodology that thrives on optimisation and simulation and we formulate some managerial guidelines to define an appropriate hiring and overtime policy.
PubDate: 20170313
DOI: 10.1007/s1095101705126
 Authors: Jonas Ingels; Broos Maenhout
 Twoagent flowshop scheduling to maximize the weighted number of
justintime jobs Authors: Yunqiang Yin; T. C. E. Cheng; DuJuan Wang; ChinChia Wu
Abstract: We consider the scheduling problem in which two agents (agents A and B), each having its own job set (containing the Ajobs and Bjobs, respectively), compete to process their own jobs in a twomachine flowshop. Each agent wants to maximize a certain criterion depending on the completion times of its jobs only. Specifically, agent A desires to maximize either the weighted number of justintime (JIT) Ajobs that are completed exactly on their due dates or the maximum weight of the JIT Ajobs, while agent B wishes to maximize the weighted number of JIT Bjobs. Evidently four optimization problems can be formulated by treating the two agents’ criteria as objectives and constraints of the corresponding optimization problems. We focus on the problem of finding the Paretooptimal schedules and present a bicriterion analysis of the problem. Solving this problem also solves the other three problems of bicriterion scheduling as a byproduct. We show that the problems under consideration are either polynomially or pseudopolynomially solvable. In addition, for each pseudopolynomialtime solution algorithm, we show how to convert it into a twodimensional fully polynomialtime approximation scheme for determining an approximate Paretooptimal schedule. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.
PubDate: 20170304
DOI: 10.1007/s1095101705117
 Authors: Yunqiang Yin; T. C. E. Cheng; DuJuan Wang; ChinChia Wu
 Flexible bandwidth assignment with application to optical networks
 Authors: Hadas Shachnai; Ariella Voloshin; Shmuel Zaks
Abstract: We introduce two scheduling problems, the flexible bandwidth allocation problem ( \(\textsc {FBAP}\) ) and the flexible storage allocation problem ( \(\textsc {FSAP}\) ). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In \(\textsc {FBAP}\) , the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in \(\textsc {FSAP}\) we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore \(\text {NPhard}\) . Our main results are a 3approximation algorithm for \(\textsc {FBAP}\) and a \((3+\epsilon )\) approximation algorithm for \(\textsc {FSAP}\) , for any fixed \(\epsilon >0 \) . These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a \((2+\epsilon )\) approximation algorithm for \(\textsc {SAP}\) , for any fixed \(\epsilon >0 \) , thus improving the best known ratio of \(\frac{2e1}{e1} + \epsilon \) . Our study is motivated also by critical resource allocation problems arising in alloptical networks.
PubDate: 20170304
DOI: 10.1007/s1095101705144
 Authors: Hadas Shachnai; Ariella Voloshin; Shmuel Zaks
 Improved algorithms for resource allocation under varying capacity
 Authors: Venkatesan T. Chakaravarthy; Anamitra R. Choudhury; Shalmoli Gupta; Sambudha Roy; Yogish Sabharwal
Abstract: 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 by starting time, ending time, profit and resource requirement. A feasible solution selects a subset of job instances such that at any timeslot, the total requirement by the chosen instances does not exceed the resource available at that timeslot, and at most one instance is chosen for each job. The above problem falls under the wellstudied framework of unsplittable flow problem on line. The generalized notion of scheduling possibilities captures the standard setting concerned with release times and deadlines. We present improved algorithms based on the primal–dual paradigm, where the improvements are in terms of approximation ratio, running time and simplicity.
PubDate: 20170216
DOI: 10.1007/s1095101705153
 Authors: Venkatesan T. Chakaravarthy; Anamitra R. Choudhury; Shalmoli Gupta; Sambudha Roy; Yogish Sabharwal
 Mathematical models for the berth allocation problem in dry bulk terminals
 Authors: Andreas T. Ernst; Ceyda Oğuz; Gaurav Singh; Gita Taherkhani
Abstract: Port terminals processing large cargo vessels play an important role in bulk material supply chains. This paper addresses the question of how to allocate vessels to a location on a berth and the sequence in which the vessels should be processed in order to minimize delays. An important consideration in the berth allocation is the presence of tidal constraints that limit the departure of fully loaded vessels from the terminal. We show how the berth allocation problem can be modeled as an integer program and discuss a number of ways to tighten the formulation in order to make it computationally tractable. In addition, a twophase method is developed for solving these problems. Empirical computational results demonstrate an order of magnitude improvement in performance. The two new approaches can solve significantly larger instances, producing faster solutions for small instances and much tighter bounds for large instances.
PubDate: 20170216
DOI: 10.1007/s1095101705108
 Authors: Andreas T. Ernst; Ceyda Oğuz; Gaurav Singh; Gita Taherkhani
 Single machine scheduling with job delivery to multiple customers
 Authors: Jianming Dong; Xueshi Wang; Jueliang Hu; Guohui Lin
Abstract: 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 representing the fraction of space it occupies on the vehicle. The vehicle delivers a shipment from the machine to a customer and has to return back to the machine for delivering the next shipment. It takes different constant time for the round trips between the machine and the different customers. The goal is to minimize the makespan, by that time all the jobs are processed and delivered to their respective customers, and the vehicle returns back to the machine. We propose a 2approximation algorithm for the general case; when there are only two customers, we present an improved 5/3approximation algorithm. The design and performance analysis of these two algorithms integrate several known results and techniques for the single machine scheduling problem, the binpacking problem, and the knapsack problem.
PubDate: 20170215
DOI: 10.1007/s1095101705082
 Authors: Jianming Dong; Xueshi Wang; Jueliang Hu; Guohui Lin
 The equivalence of two classical list scheduling algorithms for dependent
typed tasks with release dates, due dates and precedence delays Authors: Aurélien Carlier; Claire Hanen; Alix Munier Kordon
Abstract: We consider a finite set of unit time execution tasks with release dates, due dates and precedence delays. The machines are partitioned into k classes. Each task requires one machine from a fixed class to be executed. The problem is the existence of a feasible schedule. This general problem is known to be \(\mathcal {NP}\) complete; many studies were devoted to the determination of polynomial time algorithms for some special subcases, most of them based on a particular list schedule. The Garey–Johnson and Leung–Palem–Pnueli algorithms (respectively GJ and LPP in short) are both improving the due dates to build a priority list. They are modifying them using necessary conditions until a fixed point is reached. The present paper shows that these two algorithms are different implementations of the same generic one. The main consequence is that all the results valid for GJ algorithm are also for LPP and vice versa.
PubDate: 20170214
DOI: 10.1007/s1095101605078
 Authors: Aurélien Carlier; Claire Hanen; Alix Munier Kordon
 Journal of Scheduling (2017)
 Authors: Edmund Burke; Michael Pinedo
PubDate: 20170202
DOI: 10.1007/s1095101705091
 Authors: Edmund Burke; Michael Pinedo
 Online interval scheduling with a bounded number of failures
 Authors: Marco Bender; Clemens Thielen; Stephan Westphal
Abstract: We consider the problem of scheduling intervals on m identical machines where each interval can be seen as a job with fixed start and end time. The goal is to accept a maximum cardinality subset of the given intervals and assign these intervals to the machines subject to the constraint that no two intervals assigned to the same machine overlap. We analyze an online version of this problem where, initially, a set of n potential intervals and an upper bound k on the number of failing intervals is given. If an interval fails, it can be accepted neither by the online algorithm nor by the adversary. An online algorithm learns that an interval fails at the time when it is supposed to be started. If a nonfailing interval is accepted, it cannot be aborted and must be processed nonpreemptively until completion. For different settings of this problem, we present deterministic and randomized online algorithms and prove lower bounds on the competitive ratio.
PubDate: 20170113
DOI: 10.1007/s1095101605069
 Authors: Marco Bender; Clemens Thielen; Stephan Westphal
 New strategies for stochastic resourceconstrained project scheduling
 Authors: Salim Rostami; Stefan Creemers; Roel Leus
Abstract: We study the stochastic resourceconstrained 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 classes described in the literature. A policy in this new class makes a number of a priori decisions in a preprocessing phase, while the remaining scheduling decisions are made online. A twophase local search algorithm is proposed to optimize within the class. Our computational results show that the algorithm has been efficiently tuned toward finding highquality solutions and that it outperforms all existing algorithms for large instances. The results also indicate that the optimality gap even within the larger class of elementary policies is very small.
PubDate: 20170112
DOI: 10.1007/s109510160505x
 Authors: Salim Rostami; Stefan Creemers; Roel Leus
 Online bin stretching with three bins
 Authors: Martin Böhm; Jiří Sgall; Rob van Stee; Pavel Veselý
Abstract: Online bin stretching is a semionline variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for online bin stretching with a stretching factor of \(11/8 = 1.375\) for three bins. Additionally, we present a lower bound of \(45/33 = 1.\overline{36}\) for online bin stretching on three bins and a lower bound of 19/14 for four and five bins that were discovered using a computer search.
PubDate: 20170111
DOI: 10.1007/s109510160504y
 Authors: Martin Böhm; Jiří Sgall; Rob van Stee; Pavel Veselý
 New challenges in scheduling theory
 Authors: Jacek Blazewicz; Benjamin Moseley; Erwin Pesch; Denis Trystram; Guochuan Zhang
PubDate: 20161130
DOI: 10.1007/s109510160503z
 Authors: Jacek Blazewicz; Benjamin Moseley; Erwin Pesch; Denis Trystram; Guochuan Zhang
 Scheduling shipments in closedloop sortation conveyors
 Authors: Dirk Briskorn; Simon Emde; Nils Boysen
Abstract: At the very core of most automated sorting systems— for example, at airports for baggage handling and in parcel distribution centers for sorting mail—we find closedloop tilt tray sortation conveyors. In such a system, trays are loaded with cargo as they pass through loading stations, and are later tilted upon reaching the outbound container dedicated to a shipment’s destination. This paper addresses the question of whether the simple decision rules typically applied in the real world when deciding which parcel should be loaded onto what tray are, indeed, a good choice. We formulate a shortterm deterministic scheduling problem where a finite set of shipments must be loaded onto trays such that the makespan is minimized. We consider different levels of flexibility in how to arrange shipments on the feeding conveyors, and distinguish between unidirectional and bidirectional systems. In a comprehensive computational study, we compare these sophisticated optimization procedures with widespread rules of thumb, and find that the latter perform surprisingly well. For almost all problem settings, some priority rule can be identified which leads to a lowsingledigit optimality gap. In addition, we systematically evaluate the performance gains promised by different sorter layouts.
PubDate: 20161018
DOI: 10.1007/s1095101604985
 Authors: Dirk Briskorn; Simon Emde; Nils Boysen