
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 [2336 journals] 
 Finding optimal tour schedules on transportation paths under extended time
window constraints Authors: Stefan Bock
Pages: 527  546
Abstract: Abstract This paper addresses timecritical routing on a given path under release dates and deadline restrictions, while the minimization of the total weighted completion time is pursued. Since there may be destinations with flexible picking area resources that enable a delivery of goods before the defined release date at no additional costs, the wellknown LineTraveling Repairman problem (LineTRPTW) is extended into the LineTRPeTW. The LineTRPeTW has various practical applications, such as, for example, the tour planning of an inland container ship along a river or that of a vehicle along a coastline. Although the feasibility variant of the LineTRPTW/LineTRPeTW is known to be strongly \({\mathcal {NP}}\) hard, a first practically applicable Branch&Bound procedure is generated. By making use of different dominance rules and lower bounds, a comprehensive computational study proves that instances comprising up to 200 requests and locations are solved to optimality in reasonable time. Moreover, the paper analyzes the complexity of the simpler variant with relaxed release dates at all customer locations. This relaxed variant provides tight lower bounds. Furthermore, the complexity analysis shows that the relaxed problem variant is binary \({\mathcal {NP}}\) hard even if deadlines are ignored, but can be efficiently solved by a specific Dynamic Programming approach that runs in pseudopolynomial time.
PubDate: 20161001
DOI: 10.1007/s1095101604811
Issue No: Vol. 19, No. 5 (2016)
 Authors: Stefan Bock
 Worstcase performance analysis of some approximation algorithms for
minimizing makespan and flowtime Authors: Peruvemba Sundaram Ravi; Levent Tunçel; Michael Huang
Pages: 547  561
Abstract: Abstract In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtimeoptimal schedules, called the LD algorithm, has a simple worstcase performance bound: \(\frac{5m2}{4m1}\) , where m is the number of machines. We study the structure of potential minimal counterexamples to this conjecture, provide some new tools and techniques for the analysis of such algorithms, and prove that to verify the conjecture, it suffices to analyze the following case: for every \(m \ge 4\) , \(n \in \{4m, 5m\}\) , where n is the number of jobs.
PubDate: 20161001
DOI: 10.1007/s1095101504674
Issue No: Vol. 19, No. 5 (2016)
 Authors: Peruvemba Sundaram Ravi; Levent Tunçel; Michael Huang
 A reclaimer scheduling problem arising in coal stockyard management
 Authors: Enrico Angelelli; Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
Pages: 563  582
Abstract: We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm.
PubDate: 20161001
DOI: 10.1007/s109510150436y
Issue No: Vol. 19, No. 5 (2016)
 Authors: Enrico Angelelli; Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
 Scheduling parallelmachine batch operations to maximize ontime delivery
performance Authors: Shubin Xu; James C. Bean
Pages: 583  600
Abstract: Abstract In this paper we study the problem of minimizing total weighted tardiness, a proxy for maximizing ontime delivery performance, on parallel nonidentical batch processing machines. We first formulate the (primal) problem as a nonlinear integer programming model. We then show that the primal problem can be solved exactly by solving a corresponding dual problem with a nonlinear relaxation. Since both the primal and the dual problems are NPhard, we use genetic algorithms, based on random keys and multiple choice encodings, to heuristically solve them. We find that the genetic algorithms consistently outperform a standard mathematical programming package in terms of solution quality and computation time. We also compare the smaller problem instances to a breadthfirst tree search algorithm that gives evidence of the quality of the solutions.
PubDate: 20161001
DOI: 10.1007/s1095101504496
Issue No: Vol. 19, No. 5 (2016)
 Authors: Shubin Xu; James C. Bean
 An analysis of the nonpreemptive mixedcriticality matchup scheduling
problem Authors: Zdeněk Hanzálek; Tomáš Tunys; Přemysl Šůcha
Pages: 601  607
Abstract: Abstract Many applications have a mixedcriticality nature. They contain tasks with a different criticality, meaning that a task with a lower criticality can be skipped if a task with a higher criticality needs more time to be executed. This paper deals with a mixedcriticality scheduling problem where each task has a criticality given by a positive integer number. The exact processing time of the task is not known. Instead, we use different upper bounds of the processing time for different criticality levels of the schedule. A schedule with different criticality levels is generated offline, but its online execution switches among the criticality levels depending on the actual values of the processing times. The advantage is that after the transient prolongation of a higher criticality task, the system is able to match up with the schedule on a lower criticality level. While using this model, we achieve significant schedule efficiency (assuming that the prolongation of the higher criticality task rarely occurs), and at the same time, we are able to grant a sufficient amount of time to higher criticality tasks (in such cases, some of the lower criticality tasks may be skipped). This paper shows a motivation for the nonpreemptive mixedcriticality matchup scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3partition problem, we prove the problem to be \(\mathcal {NP}\) hard in the strong sense even when the release dates and deadlines are dropped and only two criticality levels are considered.
PubDate: 20161001
DOI: 10.1007/s109510160468y
Issue No: Vol. 19, No. 5 (2016)
 Authors: Zdeněk Hanzálek; Tomáš Tunys; Přemysl Šůcha
 Highmultiplicity scheduling on one machine with forbidden start and
completion times Authors: Michaël Gabay; Christophe Rapine; Nadia Brauner
Pages: 609  616
Abstract: Abstract We are interested in a single machine scheduling problem where jobs can neither start nor end on some specified instants, and the aim is to minimize the makespan. This problem models the situation where an additional resource, subject to unavailability constraints, is required to start and to finish a job. We consider in this paper the highmultiplicity version of the problem, when the input is given using a compact encoding. We present a polynomial time algorithm for large diversity instances (when the number of different processing times is greater than the number of forbidden instants). We also show that this problem is fixedparameter tractable when the number of forbidden instants is fixed, regardless of jobs characteristics.
PubDate: 20161001
DOI: 10.1007/s109510160475z
Issue No: Vol. 19, No. 5 (2016)
 Authors: Michaël Gabay; Christophe Rapine; Nadia Brauner
 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 jobs and maintenance activities subject to jobdependent
machine deteriorations Authors: Liliana Grigoriu; Dirk Briskorn
Abstract: Abstract This paper considers machine scheduling that integrates machine deterioration caused by jobs and, consequently, maintenance activities. The maintenance state of the machine is represented by a maintenance level which drops by a certain, possibly jobdependent amount while jobs are processed. A maintenance level of less than zero is associated with the machine’s breakdown and is therefore forbidden. Hence, maintenance activities that raise the maintenance level may become necessary and have to be scheduled additionally. We consider the objective to minimize the makespan throughout the paper. For the single machine case, we provide a lineartime approximation algorithm with worstcase a bound of 5/4, and comment on how an FPTAS from previous literature can be employed to apply to our problem. Due to problem similarity, these results also apply to the minimum subset sum problem, and the 5/4 lineartime approximation algorithm is an improvement over the 5/4 quadratictime approximation algorithm of Güntzer and Jungnickel. For the general problem with multiple machines, we provide approximability results, two fast heuristics, an approximation algorithm with an instancedependent approximation factor and a computational study evaluating the heuristics.
PubDate: 20161112
DOI: 10.1007/s1095101605020
 Authors: Liliana Grigoriu; Dirk Briskorn
 Approximation for scheduling on uniform nonsimultaneous parallel machines
 Authors: Liliana Grigoriu; Donald K. Friesen
Abstract: Abstract We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worstcase bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worstcase approximation bounds for scheduling on nonsimultaneous uniform machines and show that worstcase approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines.
PubDate: 20161111
DOI: 10.1007/s1095101605011
 Authors: Liliana Grigoriu; Donald K. Friesen
 Energyefficient scheduling and routing via randomized rounding
 Authors: Evripidis Bampis; Alexander Kononov; Dimitrios Letsios; Giorgio Lucarelli; Maxim Sviridenko
Abstract: 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: 20161028
DOI: 10.1007/s1095101605002
 Authors: Evripidis Bampis; Alexander Kononov; Dimitrios Letsios; Giorgio Lucarelli; Maxim Sviridenko
 Scheduling shipments in closedloop sortation conveyors
 Authors: Dirk Briskorn; Simon Emde; Nils Boysen
Abstract: 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
 A hybrid multiobjective immune algorithm for predictive and reactive
scheduling Authors: Iwona Paprocka; Bożena Skołud
Abstract: Abstract The high productivity of a production process has a major impact on the reduction of the production cost and on a quick response to changing demands. Information about a failurefree machine operation time obtained in advance allows the users to plan preventive maintenance in order to keep the machine in a good operational condition. The introduction of maintenance work into a schedule reduces the frequency of unpredicted breaks caused by machine failures. It also results in higher productivity and intime production. The foregoing of this constitutes the main idea of the predictive scheduling method proposed in the paper. Rescheduling of disrupted operations, with a minimal impact on the stability and robustness of a schedule, is the main idea of the reactive scheduling method proposed. The first objective of the paper is to present a hybrid multiobjective immune algorithm (HMOIA) aided by heuristics: a minimal impact of disrupted operation on the schedule (MIDOS) for predictive scheduling and a minimal impact of rescheduled operation on the schedule (MIROS) for reactive scheduling. The second objective is to compare the HMOIA with various methods for predictive and reactive scheduling. The HMOIA + MIDOS is compared to two algorithms, identified in reference publications: (1) an algorithm based on priority rules: the least flexible job first (LFJ) and the longest processing time (LPT) (2) an Average Slack Method. The HMOIA + MIROS is compared to: (1) an algorithm based on priority rules: the LFJ and LPT and (2) Shifted GapReduction. This paper presents the research results and computer simulations.
PubDate: 20160926
DOI: 10.1007/s1095101604949
 Authors: Iwona Paprocka; Bożena Skołud
 Scheduling reclaimers serving a stock pad at a coal terminal
 Authors: Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
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: 20160923
DOI: 10.1007/s1095101604958
 Authors: Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
 Optimizing railway crew schedules with fairness preferences
 Authors: Silke Jütte; Daniel Müller; Ulrich W. Thonemann
Abstract: 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: 20160923
DOI: 10.1007/s1095101604994
 Authors: Silke Jütte; Daniel Müller; Ulrich W. Thonemann
 Single machine scheduling with a generalized jobdependent cumulative
effect Authors: Kabir Rustogi; Vitaly A. Strusevich
Abstract: Abstract We consider a single machine scheduling problem with changing processing times. The processing conditions are subject to a general cumulative effect, in which the processing time of a job depends on the sum of certain parameters associated with previously scheduled jobs. In previous papers, these parameters are assumed to be equal to the normal processing times of jobs, which seriously limits the practical application of this model. We further generalize this model by allowing every job to respond differently to these cumulative effects. For the introduced model, we solve the problem of minimizing the makespan, with and without precedence constraints. For the problem without precedence constraints, we also consider a situation in which a maintenance activity is included in the schedule, which can improve the processing conditions of the machine, not necessarily to its original state. The resulting problem is reformulated as a variant of a Boolean programming problem with a quadratic objective, known as a halfproduct, which allows us to develop a fully polynomialtime approximation scheme with the best possible running time.
PubDate: 20160923
DOI: 10.1007/s1095101604976
 Authors: Kabir Rustogi; Vitaly A. Strusevich
 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
Abstract: 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: 20160922
DOI: 10.1007/s1095101604967
 Authors: Konstantinos G. Zografos; Michael A. Madas; Konstantinos N. Androutsopoulos
 Scheduling operating rooms: achievements, challenges and pitfalls
 Authors: Michael Samudra; Carla Van Riet; Erik Demeulemeester; Brecht Cardoen; Nancy Vansteenkiste; Frank E. Rademakers
Abstract: Abstract In hospitals, the operating room (OR) is a particularly expensive facility and thus efficient scheduling is imperative. This can be greatly supported by using advanced methods that are discussed in the academic literature. In order to help researchers and practitioners to select new relevant articles, we classify the recent OR planning and scheduling literature into tables regarding patient type, used performance measures, decisions made, OR up and downstream facilities, uncertainty, research methodology and testing phase. Based on these classifications, we identify trends and promising topics. Additionally, we recognize three common pitfalls that hamper the adoption of research results by stakeholders: the lack of a clear choice of authors on whether to target researchers (contributing advanced methods) or practitioners (providing managerial insights), the use of illfitted performance measures in models and the failure to understandably report on the hospital setting and methodrelated assumptions. We provide specific guidelines that help to avoid these pitfalls. First, we show how to build up an article based on the choice of the target group (i.e., researchers or practitioners). Making a clear distinction between target groups impacts the problem setting, the research task, the reported findings, and the conclusions. Second, we discuss points that need to be considered by researchers when deciding on the used performance measures. Third, we list the assumptions that need to be included in articles in order to enable readers to decide whether the presented research is relevant to them.
PubDate: 20160906
DOI: 10.1007/s1095101604896
 Authors: Michael Samudra; Carla Van Riet; Erik Demeulemeester; Brecht Cardoen; Nancy Vansteenkiste; Frank E. Rademakers
 Optimizationbased resource allocation for software as a service
application in cloud computing Authors: Chunlin Li; Yun Chang Liu; Xin Yan
Abstract: 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: 20160819
DOI: 10.1007/s109510160491z
 Authors: Chunlin Li; Yun Chang Liu; Xin Yan
 Twomachine flowshop scheduling with threeoperation jobs subject to a
fixed job sequence Authors: Bertrand M. T. Lin; F. J. Hwang; Jatinder N. D. Gupta
Abstract: Abstract This paper studies the problem of scheduling threeoperation jobs in a twomachine flowshop subject to a predetermined job processing sequence. Each job has two preassigned operations, which are to be performed on their respective dedicated machines, and a flexible operation, which may be processed on either of the two machines subject to the processing order as specified. Five standard objective functions, including the makespan, the maximum lateness, the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs are considered. We show that the studied problem for either of the five considered objective functions is ordinary NPhard, even if the processing times of the preassigned operations are zero for all jobs. A pseudopolynomial time dynamic programming framework, coupled with brief numerical experiments, is then developed for all the addressed performance metrics with different run times.
PubDate: 20160811
DOI: 10.1007/s109510160493x
 Authors: Bertrand M. T. Lin; F. J. Hwang; Jatinder N. D. Gupta
 Open Shop Scheduling with Synchronization
 Authors: C. Weiß; S. Waldherr; S. Knust; N. V. Shakhlevich
Abstract: Abstract In this paper, we study open shop scheduling problems with synchronization. This model has the same features as the classical open shop model, where each of the n jobs has to be processed by each of the m machines in an arbitrary order. Unlike the classical model, jobs are processed in synchronous cycles, which means that the m operations of the same cycle start at the same time. Within one cycle, machines which process operations with smaller processing times have to wait until the longest operation of the cycle is finished before the next cycle can start. Thus, the length of a cycle is equal to the maximum processing time of its operations. In this paper, we continue the line of research started by Weiß et al. (Discrete Appl Math 211:183–203, 2016). We establish new structural results for the twomachine problem with the makespan objective and use them to formulate an easier solution algorithm. Other versions of the problem, with the total completion time objective and those which involve due dates or deadlines, turn out to be NPhard in the strong sense, even for \(m=2\) machines. We also show that relaxed models, in which cycles are allowed to contain less than m jobs, have the same complexity status.
PubDate: 20160808
DOI: 10.1007/s1095101604900
 Authors: C. Weiß; S. Waldherr; S. Knust; N. V. Shakhlevich