
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 [2354 journals] 
 Minimizing worstcase and averagecase makespan over scenarios
 Authors: Esteban Feuerstein; Alberto MarchettiSpaccamela; Frans Schalekamp; René Sitters; Suzanne van der Ster; Leen Stougie; Anke van Zuylen
Pages: 545  555
Abstract: We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all scenarios in an explicitly given set. Each scenario is a subset of jobs that must be executed in that scenario. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. We also consider some (easier) special cases. Combinatorial optimization problems under scenarios in general, and scheduling problems under scenarios in particular, have seen only limited research attention so far. With this paper, we make a step in this interesting research direction.
PubDate: 20171201
DOI: 10.1007/s109510160484y
Issue No: Vol. 20, No. 6 (2017)
 Authors: Esteban Feuerstein; Alberto MarchettiSpaccamela; Frans Schalekamp; René Sitters; Suzanne van der Ster; Leen Stougie; Anke van Zuylen
 Open Shop Scheduling with Synchronization
 Authors: C. Weiß; S. Waldherr; S. Knust; N. V. Shakhlevich
Pages: 557  581
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: 20171201
DOI: 10.1007/s1095101604900
Issue No: Vol. 20, No. 6 (2017)
 Authors: C. Weiß; S. Waldherr; S. Knust; N. V. Shakhlevich
 Single machine scheduling with a generalized jobdependent cumulative
effect Authors: Kabir Rustogi; Vitaly A. Strusevich
Pages: 583  592
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: 20171201
DOI: 10.1007/s1095101604976
Issue No: Vol. 20, No. 6 (2017)
 Authors: Kabir Rustogi; Vitaly A. Strusevich
 Approximation for scheduling on uniform nonsimultaneous parallel machines
 Authors: Liliana Grigoriu; Donald K. Friesen
Pages: 593  600
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: 20171201
DOI: 10.1007/s1095101605011
Issue No: Vol. 20, No. 6 (2017)
 Authors: Liliana Grigoriu; Donald K. Friesen
 Online bin stretching with three bins
 Authors: Martin Böhm; Jiří Sgall; Rob van Stee; Pavel Veselý
Pages: 601  621
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: 20171201
DOI: 10.1007/s109510160504y
Issue No: Vol. 20, No. 6 (2017)
 Authors: Martin Böhm; Jiří Sgall; Rob van Stee; Pavel Veselý
 Scheduling multipacket frames with frame deadlines
 Authors: Łukasz Jeż; Yishay Mansour; Boaz PattShamir
Pages: 623  634
Abstract: We consider scheduling information units called frames, each with a delivery deadline. Frames consist of packets, which arrive online in a roughly periodic fashion, and compete on allocation of transmission slots. A frame is deemed useful only if all its packets are delivered before its deadline. We focus on a “proportional” variant, where the value of each frame is proportional to its size, but the sizes and periods of the frames are arbitrary. We give a constantcompetitive algorithm for this setting, assuming bounded jitter and some slack in the frames’ deadlines, the latter of which is necessary. Using standard techniques, our algorithm yields polylogcompetitive algorithms for general instances with slack and bounded jitter.
PubDate: 20171201
DOI: 10.1007/s1095101705224
Issue No: Vol. 20, No. 6 (2017)
 Authors: Łukasz Jeż; Yishay Mansour; Boaz PattShamir
 Staff and machine shift scheduling in a German potash mine
 Authors: Marco Schulze; Jürgen Zimmermann
Pages: 635  656
Abstract: This paper addresses a shortterm production scheduling problem that arises in a German potash underground mine. In particular, we consider a combined staff and machine scheduling problem where mining operations have to be assigned to resources and scheduled simultaneously. The resources are composed of the machines and workers that are available in the upcoming working shift. Due to the given application, several miningspecific requirements have to be taken into account, e.g., how to handle mining operations within the same underground location. In order to solve the problem, we propose a construction procedure that is extended to a multistart algorithm. In a computational study, we conduct experiments on random as well as realworld instances.
PubDate: 20171201
DOI: 10.1007/s109510170527z
Issue No: Vol. 20, No. 6 (2017)
 Authors: Marco Schulze; Jürgen Zimmermann
 LP rounding and combinatorial algorithms for minimizing active and busy
time Authors: Jessica Chang; Samir Khuller; Koyel Mukherjee
Pages: 657  680
Abstract: We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline, and required processing length. The jobs need to be scheduled on a machine so that at most g jobs are active at any given time. The duration for which a machine is active (i.e., “on”) is referred to as its active time. The goal is to find a feasible schedule for all jobs, minimizing the total active time. When preemption is allowed at integer time points, we show that a minimal feasible schedule already yields a 3approximation (and this bound is tight) and we further improve this to a 2approximation via LP rounding techniques. Our second contribution is for the nonpreemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NPhard, we allow for an unbounded number of virtual machines, each having capacity of g. This problem is known as the busy time problem in the literature and a 4approximation is known for this problem. We develop a new combinatorial algorithm that gives a 3approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields an algorithm that is 2approximate.
PubDate: 20171201
DOI: 10.1007/s1095101705313
Issue No: Vol. 20, No. 6 (2017)
 Authors: Jessica Chang; Samir Khuller; Koyel Mukherjee
 Reordering buffer management with advice
 Authors: Anna Adamaszek; Marc P. Renault; Adi Rosén; Rob van Stee
Pages: 423  442
Abstract: In the reordering buffer management problem, a sequence of colored items arrives at a service station to be processed. Each color change between two consecutively processed items generates some cost. A reordering buffer of capacity k items can be used to preprocess the input sequence in order to decrease the number of color changes. The goal is to find a scheduling strategy that, using the reordering buffer, minimizes the number of color changes in the given sequence of items. We consider the problem in the setting of online computation with advice. In this model, the color of an item becomes known only at the time when the item enters the reordering buffer. Additionally, together with each item entering the buffer, we get a fixed number of advice bits, which can be seen as information about the future or as information about an optimal solution (or an approximation thereof) for the whole input sequence. We show that for any \(\varepsilon > 0\) there is a \((1+\varepsilon )\) competitive algorithm for the problem which uses only a constant (depending on \(\varepsilon \) ) number of advice bits per input item. This also immediately implies a \((1+\varepsilon )\) approximation algorithm which has \(2^{O(n\log 1/\varepsilon )}\) running time (this should be compared to the trivial optimal algorithm which has a running time of \(k^{O(n)}\) ). We complement the above result by presenting a lower bound of \(\varOmega (\log k)\) bits of advice per request for any 1competitive algorithm.
PubDate: 20171001
DOI: 10.1007/s1095101604878
Issue No: Vol. 20, No. 5 (2017)
 Authors: Anna Adamaszek; Marc P. Renault; Adi Rosén; Rob van Stee
 Scheduling cleaning activities on trains by minimizing idle times
 Authors: Enrico Bartolini; Mauro Dell’Amico; Manuel Iori
Pages: 493  506
Abstract: We consider a workforce scheduling problem which consists of determining optimal working shifts for cleaning personnel at a rail station. Trains arrive and depart according to a specified schedule and require a given amount of cleaning time from the personnel before their departure from the station. Working shifts must specify a sequence of trains to be cleaned by a worker together with corresponding cleaning times and are subject to contract regulations which impose both a minimum and a maximum duration of the shift. We model the problem as a mixedinteger program with a pseudopolynomial number of variables and propose an exponentially sized reformulation obtained through Dantzig–Wolfe reformulation. The reformulation is strengthened by valid inequalities and used to compute lower bounds on the optimal cost. A heuristic algorithm based on column generation and variable fixing is then proposed and computationally evaluated on both a set of instances derived from real data and a larger set of randomly generated ones. The reported computational results show that the algorithm provides solutions very close to the optimal ones within 1 h of computing time.
PubDate: 20171001
DOI: 10.1007/s1095101705171
Issue No: Vol. 20, No. 5 (2017)
 Authors: Enrico Bartolini; Mauro Dell’Amico; Manuel Iori
 Scheduling meets n fold integer programming
 Authors: Dušan Knop; Martin Koutecký
Abstract: Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NPhard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In this paper, we continue this study and show that several additional cases of fundamental scheduling problems are fixedparameter tractable for some natural parameters. Our main tool is nfold integer programming, a recent variable dimension technique which we believe to be highly relevant for the parameterized complexity community. This paper serves to showcase and highlight this technique. Specifically, we show the following four scheduling problems to be fixedparameter tractable, where \(p_{\max }\) is the maximum processing time of a job and \(w_{\max }\) is the maximum weight of a job: Makespan minimization on uniformly related machines ( \(Q C_{\max }\) ) parameterized by \(p_{\max }\) , Makespan minimization on unrelated machines ( \(R C_{\max }\) ) parameterized by \(p_{\max }\) and the number of kinds of machines (defined later), Sum of weighted completion times minimization on unrelated machines ( \(R \sum w_jC_j\) ) parameterized by \(p_{\max }+w_{\max }\) and the number of kinds of machines, The same problem, \(R \sum w_jC_j\) , parameterized by the number of distinct job times and the number of machines.
PubDate: 20171115
DOI: 10.1007/s1095101705500
 Authors: Dušan Knop; Martin Koutecký
 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
 An algorithm for multiagent scheduling to minimize the makespan on m
parallel machines Authors: Manzhan Gu; Jinwei Gu; Xiwen Lu
Abstract: This paper considers a multiagent scheduling problem, in which each agent has a set of nonpreemptive jobs, and jobs of all agents are to be processed on m identical parallel machines. The objective is to find a schedule to minimize the makespan of each agent. For an agent, the definition of \(\alpha \) point is introduced, based on which an approximation algorithm is proposed for the problem. In the obtained schedule, the agent with the ith smallest \(\alpha \) point value is the ith completed agent, and the agent’s completion time is at most \(i+ \left( \frac{1}{3}\frac{1}{3m}\right) \) times its minimum makespan. Finally, we show the performance analysis is tight.
PubDate: 20171020
DOI: 10.1007/s1095101705469
 Authors: Manzhan Gu; Jinwei Gu; Xiwen Lu
 An implicit model for multiactivity shift scheduling problems
 Authors: Sana Dahmen; Monia Rekik; François Soumis
Abstract: We consider a multiactivity shift scheduling problem where the objective is to construct anonymous multiactivity shifts that respect union rules, satisfy the demand and minimize workforce costs. An implicit approach using adapted forward and backward constraints is proposed that integrates both the shift construction and the activity assignment problems. Our computational study shows that using the branchandbound procedure of CPLEX 12.6 on the proposed implicit model yields optimal solutions in relatively short times for environments including up to 2970 millions of explicit shifts. Our implicit model is compared to the grammarbased implicit model proposed by Côté et al. (Manag Sci 57(1):151–163, 2011b) on a large set of instances. The results prove that both implicit models have their strengths and weaknesses and are more or less efficient depending on the scheduling environment.
PubDate: 20171011
DOI: 10.1007/s109510170544y
 Authors: Sana Dahmen; Monia Rekik; François Soumis
 Singlemachine scheduling with workloaddependent tool change durations
and equal processing time jobs to minimize total completion time Authors: Zhijun Xu; Dehua Xu
Abstract: We consider a singlemachine tool change scheduling problem where tool change durations are workloaddependent. The processing times of all the jobs are the same. The objective is to determine the number of tool change activities, the start time and the completion time of each tool change activity jointly and schedule all the jobs to the machine such that the total completion time of the jobs is minimized. For the case where the tool change duration function is concave, we present a linear time optimal algorithm. For the case where the tool change duration function is convex, we convert it into a convex integer quadratic programming problem with fixed dimension and then propose two polynomial time algorithms for it. We also study some special cases for which optimal schedules can be obtained directly. For the case where the tool change duration function is linear, we present all the optimal schedules.
PubDate: 20171005
DOI: 10.1007/s109510170543z
 Authors: Zhijun Xu; Dehua Xu
 Twostage hybrid flowshop scheduling with simultaneous processing machines
 Authors: Bailin Wang; Kai Huang; Tieke Li
Abstract: Simultaneous processing machines, common in processing industries such as steel and food production, can process several jobs simultaneously in the firstin, firstout manner. However, they are often highly energyconsuming. In this paper, we study a new twostage hybrid flowshop scheduling problem, with simultaneous processing machines at the first stage and a single noidle machine with predetermined job sequence at the second stage. A mixed integer programming model is proposed with the objective of minimizing the total processing time to reduce energy consumption and improve production efficiency. We give a sufficient and necessary condition to construct feasible sequencing solutions and present an effective approach to calculate the time variables for a feasible sequencing solution. Based on these results, we design a list scheduling heuristic algorithm and its improvement. Both heuristics can find an optimal solution under certain conditions with complexity O(nlogn), where n is the number of jobs. Our experiments verify the efficiency of these heuristics compared with classical heuristics in the literature and investigate the impacts of problem size and processing times.
PubDate: 20171004
DOI: 10.1007/s109510170545x
 Authors: Bailin Wang; Kai Huang; Tieke Li
 Integrated production and outbound distribution scheduling problems with
job release dates and deadlines Authors: LiangLiang Fu; Mohamed Ali Aloulou; Christian Artigues
Abstract: In this paper, we study an integrated production and outbound distribution scheduling model with one manufacturer and one customer. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to the customer. Each job has a release date and a delivery deadline. The objective of the problem is to issue a feasible integrated production and distribution schedule minimizing the transportation cost subject to the production release dates and delivery deadline constraints. We consider three problems with different ways how a job can be produced and delivered: nonsplittable production and delivery (NSP–NSD) problem, splittable production and nonsplittable delivery problem and splittable production and delivery problem. We provide polynomialtime algorithms that solve special cases of the problem. One of these algorithms allows us to compute a lower bound for the NPhard problem NSP–NSD, which we use in a branchandbound (B&B) algorithm to solve problem NSP–NSD. The computational results show that the B&B algorithm outperforms a MILP formulation of the problem implemented on a commercial solver.
PubDate: 20171004
DOI: 10.1007/s1095101705420
 Authors: LiangLiang Fu; Mohamed Ali Aloulou; Christian Artigues
 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.
 Fault tolerant scheduling of tasks of two sizes under resource
augmentation Abstract: Guaranteeing the eventual execution of tasks in machines that are prone to unpredictable crashes and restarts may be challenging, but is also of high importance. Things become even more complicated when tasks arrive dynamically and have different computational demands, i.e., processing time (or sizes). In this paper, we focus on the online task scheduling in such systems, considering one machine and at least two different task sizes. More specifically, algorithms are designed for two different task sizes while the complementary bounds hold for any number of task sizes bigger than one. We look at the latency and 1completed load competitiveness properties of deterministic scheduling algorithms under worstcase scenarios. For this, we assume an adversary, that controls the machine crashes and restarts as well as the task arrivals of the system, including their computational demands. More precisely, we investigate the effect of resource augmentation—in the form of processor speedup—in the machine’s performance, by looking at the two efficiency measures for different speedups. We first identify the threshold of the speedup under which competitiveness cannot be achieved by any deterministic algorithm, and above which there exists some deterministic algorithm that is competitive. We then propose an online algorithm, named \(\gamma \text{Burst } \) , that achieves both latency and 1completedload competitiveness when the speedup is over the threshold. This also proves that the threshold identified is also sufficient for competitiveness.
PubDate: 20170907
DOI: 10.1007/s1095101705411
 Abstract: Guaranteeing the eventual execution of tasks in machines that are prone to unpredictable crashes and restarts may be challenging, but is also of high importance. Things become even more complicated when tasks arrive dynamically and have different computational demands, i.e., processing time (or sizes). In this paper, we focus on the online task scheduling in such systems, considering one machine and at least two different task sizes. More specifically, algorithms are designed for two different task sizes while the complementary bounds hold for any number of task sizes bigger than one. We look at the latency and 1completed load competitiveness properties of deterministic scheduling algorithms under worstcase scenarios. For this, we assume an adversary, that controls the machine crashes and restarts as well as the task arrivals of the system, including their computational demands. More precisely, we investigate the effect of resource augmentation—in the form of processor speedup—in the machine’s performance, by looking at the two efficiency measures for different speedups. We first identify the threshold of the speedup under which competitiveness cannot be achieved by any deterministic algorithm, and above which there exists some deterministic algorithm that is competitive. We then propose an online algorithm, named \(\gamma \text{Burst } \) , that achieves both latency and 1completedload competitiveness when the speedup is over the threshold. This also proves that the threshold identified is also sufficient for competitiveness.