
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 [2355 journals] 
 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
 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
 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
 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
 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.