
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] 
 Online interval scheduling with a bounded number of failures
 Authors: Marco Bender; Clemens Thielen; Stephan Westphal
Abstract: 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: 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: 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ý
 Throughput maximization for speed scaling with agreeable deadlines
 Authors: Eric Angel; Evripidis Bampis; Vincent Chau; Dimitrios Letsios
Pages: 619  625
Abstract: Abstract We study the following energyefficient scheduling problem. We are given a set of n jobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each job \(J_j\) is characterized by a processing requirement (work) \(p_j\) , a release date \(r_j\) , and a deadline \(d_j\) . We are also given a budget of energy E which must not be exceeded and our objective is to maximize the throughput (i.e., the number of jobs which are completed on time). We show that the problem can be solved optimally via dynamic programming in \(O(n^4 \log n \log P)\) time when all jobs have the same release date, where P is the sum of the processing requirements of the jobs. For the more general case with agreeable deadlines where the jobs can be ordered so that, for every \(i < j\) , it holds that \(r_i \le r_j\) and \(d_i \le d_j\) , we propose an optimal dynamic programming algorithm which runs in \(O(n^6 \log n \log P)\) time. In addition, we consider the weighted case where every job \(J_j\) is also associated with a weight \(w_j\) and we are interested in maximizing the weighted throughput (i.e., the total weight of the jobs which are completed on time). For this case, we show that the problem becomes \(\mathcal{NP}\) hard in the ordinary sense even when all jobs have the same release date and we propose a pseudopolynomial time algorithm for agreeable instances.
PubDate: 20161201
DOI: 10.1007/s109510150452y
Issue No: Vol. 19, No. 6 (2016)
 Authors: Eric Angel; Evripidis Bampis; Vincent Chau; Dimitrios Letsios
 Coscheduling algorithms for highthroughput workload execution
 Authors: Guillaume Aupy; Manu Shantharam; Anne Benoit; Yves Robert; Padma Raghavan
Pages: 627  640
Abstract: Abstract This paper investigates coscheduling algorithms for processing a set of parallel applications. Instead of executing each application one by one, using a maximum degree of parallelism for each of them, we aim at scheduling several applications concurrently. We partition the original application set into a series of packs, which are executed one by one. A pack comprises several applications, each of them with an assigned number of processors, with the constraint that the total number of processors assigned within a pack does not exceed the maximum number of available processors. The objective is to determine a partition into packs, and an assignment of processors to applications, that minimize the sum of the execution times of the packs. We thoroughly study the complexity of this optimization problem, and propose several heuristics that exhibit very good performance on a variety of workloads, whose application execution times model profiles of parallel scientific codes. We show that coscheduling leads to faster workload completion time (40 % improvement on average over traditional scheduling) and to faster response times (50 % improvement). Hence, coscheduling increases system throughput and saves energy, leading to significant benefits from both the user and system perspectives.
PubDate: 20161201
DOI: 10.1007/s109510150445x
Issue No: Vol. 19, No. 6 (2016)
 Authors: Guillaume Aupy; Manu Shantharam; Anne Benoit; Yves Robert; Padma Raghavan
 Optimizing memory allocation for multistage scheduling including setup
times Authors: Anne Benoit; Mathias Coqblin; JeanMarc Nicod; Veronika RehnSonigo
Pages: 641  658
Abstract: Abstract Mapping linear workflow applications onto a set of homogeneous processors can be optimally solved in polynomial time for the throughput objective with fewer processors than stages. This result holds true even when setup times occur in the execution and homogeneous buffers are available for the storage of intermediate results. In this kind of application, several computation stages are interconnected as a linear application graph, and each stage holds a buffer of limited size where intermediate results are stored and a processor setup time occurs when passing from one stage to another. In this paper, we tackle the problem in which the buffer sizes are not given beforehand and must be fixed before the execution to maximize the throughput within each processor. The goal of this work is to minimize the cost induced by the setup times by allocating buffers that are proportinal in size to each other. We present a closed formula to compute the optimal buffer allocation in the case of nondecreasing setup costs in the linear application. For the case of unsorted setup times, we provide competitive heuristics that are validated via extensive simulation. Three nonscalable brute force algorithms are also provided to compare heuristic approaches to optimal ones for small applications and to evaluate the relevance of our approach.
PubDate: 20161201
DOI: 10.1007/s109510150437x
Issue No: Vol. 19, No. 6 (2016)
 Authors: Anne Benoit; Mathias Coqblin; JeanMarc Nicod; Veronika RehnSonigo
 Necessary and sufficient optimality conditions for scheduling unit time
jobs on identical parallel machines Authors: Peter Brucker; Natalia V. Shakhlevich
Pages: 659  685
Abstract: Abstract In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions.
PubDate: 20161201
DOI: 10.1007/s1095101604713
Issue No: Vol. 19, No. 6 (2016)
 Authors: Peter Brucker; Natalia V. Shakhlevich
 Scheduling for electricity cost in a smart grid
 Authors: Mihai Burcea; WingKai Hon; HsiangHsuan Liu; Prudence W. H. Wong; David K. Y. Yau
Pages: 687  699
Abstract: Abstract We study an offline scheduling problem arising in demand response management in a smart grid. Consumers send in power requests with a flexible set of timeslots during which their requests can be served. For example, a consumer may request the dishwasher to operate for 1 h during the periods 8am to 11am or 2pm to 4pm. The grid controller, upon receiving power requests, schedules each request within the specified duration. The electricity cost is measured by a convex function of the load in each timeslot. The objective of the problem is to schedule all requests with the minimum total electricity cost. As a first attempt, we consider a special case in which the power requirement and the duration a for which a request needs service are both unitsize. For this problem, we present a polynomial time offline algorithm that gives an optimal solution and shows that the time complexity can be further improved if the given set of timeslots forms a contiguous interval.
PubDate: 20161201
DOI: 10.1007/s1095101504478
Issue No: Vol. 19, No. 6 (2016)
 Authors: Mihai Burcea; WingKai Hon; HsiangHsuan Liu; Prudence W. H. Wong; David K. Y. Yau
 Normalform preemption sequences for an open problem in scheduling theory
 Authors: Bo Chen; Ed Coffman; Dariusz Dereniowski; Wiesław Kubiak
Pages: 701  728
Abstract: Abstract Structural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems, but so far only rough bounds for these parameters have been derived for specific problems. This paper sharpens the bounds on these structural parameters for a wellknown open problem in the theory of preemptive scheduling: Instances consist of intrees of n unitexecutiontime jobs with release dates, and the objective is to minimize the total completion time on two processors. This is among the current, tantalizing “threshold” problems of scheduling theory: Our literature survey reveals that any significant generalization leads to an NPhard problem, but that any significant, but slight simplification leads to tractable problem with a polynomialtime solution. For the above problem, we show that the number of preemptions necessary for optimality need not exceed \(2n1\) ; that the number must be of order \({\varOmega }(\log n)\) for some instances; and that the minimum shift need not be less than \(2^{2n+1}.\) These bounds are obtained by combinatorial analysis of optimal preemptive schedules rather than by the analysis of polytope corners for linearprogram formulations of the problem, an approach to be found in earlier papers. The bounds immediately follow from a fundamental structural property called normality, by which minimal shifts of a job are exponentially decreasing functions. In particular, the first interval between a preempted job’s start and its preemption must be a multiple of 1 / 2, the second such interval must be a multiple of 1 / 4, and in general, the ith preemption must occur at a multiple of \(2^{i}\) . We expect the new structural properties to play a prominent role in finally settling a vexing, stillopen question of complexity.
PubDate: 20161201
DOI: 10.1007/s1095101504469
Issue No: Vol. 19, No. 6 (2016)
 Authors: Bo Chen; Ed Coffman; Dariusz Dereniowski; Wiesław Kubiak
 Scheduling on parallel identical machines with late work criterion:
Offline and online cases Authors: Xin Chen; Malgorzata Sterna; Xin Han; Jacek Blazewicz
Pages: 729  736
Abstract: Abstract In the paper, we consider the problem of scheduling jobs on parallel identical machines with the late work criterion and a common due date, both offline and online cases. Since the late work criterion has not been studied in the online mode so far, the analysis of the online problem is preceded by the analysis of the offline problem, whose complexity status has not been formally stated in the literature yet. Namely, for the offline mode, we prove that the twomachine problem is binary NPhard, and the general case is unary NPhard. In the online mode we assume that jobs arrive in the system one by one, i.e., we consider the online over list model. We give an algorithm with a competitive ratio being a function of the number of machines, and we prove the optimality of this approach for two identical machines.
PubDate: 20161201
DOI: 10.1007/s1095101504647
Issue No: Vol. 19, No. 6 (2016)
 Authors: Xin Chen; Malgorzata Sterna; Xin Han; Jacek Blazewicz
 Scheduling with timedependent discrepancy times
 Authors: Florian Jaehn; Helmut A. Sedding
Pages: 737  757
Abstract: Abstract In timedependent scheduling, various processing time functions are studied, yet absolute value functions have surprisingly been omitted from the discussion. Such a processing time function increases linearly with a job’s discrepancy from its ideal midtime. The objective is to find a schedule that minimizes the makespan, introducing the discrepancy time minimization problem. This singlemachine scheduling problem with timedependent processing times is motivated by optimization of walking times on a car assembly line. Its decision version is NP hard, as we show by reduction of the even–odd partition problem. For the variant with known start time, we develop several heuristics. Further insights form lower bounds and dominance rules for a branchandbound search. Numerical experiments show the performance of our algorithms on problem instances of up to 60 jobs. For the variant with common ideal midtime and flexible start time, we present a polynomialtime algorithm.
PubDate: 20161201
DOI: 10.1007/s1095101604722
Issue No: Vol. 19, No. 6 (2016)
 Authors: Florian Jaehn; Helmut A. Sedding
 On scheduling with nonincreasing time slot cost to minimize total
weighted completion time Authors: Yingchao Zhao; Xiangtong Qi; Minming Li
Pages: 759  767
Abstract: Abstract This paper addresses a recent open scheduling problem which aims to minimize the summation of total weighted completion time and the total machine time slot cost. Focusing on the case of nonincreasing time slot cost with nonpreemptive jobs, we show that the problem can be solved in polynomialtime when the time slot cost decreases with certain patterns, including linearly decreasing, decreasing concave, and decreasing convex cases. Different methodologies are used for three cases. For the linearly decreasing case, we can classify all the jobs into three categories and schedule the job sets one by one. For the decreasing concave case, we calculate each job’s worst starting time and try to make them far away from their worst starting times. For the decreasing concave case, we calculate each job’s best starting time and let them start close to their best starting times. Finally, we show that the problem is NPhard in the strong sense when the time slot cost decreases in an arbitrary way.
PubDate: 20161201
DOI: 10.1007/s1095101504629
Issue No: Vol. 19, No. 6 (2016)
 Authors: Yingchao Zhao; Xiangtong Qi; Minming Li
 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
 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
 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