for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 1974 journals)     - ANIMATION AND SIMULATION (29 journals)    - ARTIFICIAL INTELLIGENCE (98 journals)    - AUTOMATION AND ROBOTICS (97 journals)    - CLOUD COMPUTING AND NETWORKS (64 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ENGINEERING (10 journals)    - COMPUTER GAMES (15 journals)    - COMPUTER PROGRAMMING (23 journals)    - COMPUTER SCIENCE (1148 journals)    - COMPUTER SECURITY (45 journals)    - DATA BASE MANAGEMENT (12 journals)    - DATA MINING (32 journals)    - E-BUSINESS (22 journals)    - E-LEARNING (28 journals)    - ELECTRONIC DATA PROCESSING (21 journals)    - IMAGE AND VIDEO PROCESSING (41 journals)    - INFORMATION SYSTEMS (98 journals)    - INTERNET (91 journals)    - SOCIAL WEB (49 journals)    - SOFTWARE (34 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1148 journals)
 The end of the list has been reached or no journals were found for your choice.
 Journal of Scheduling   [SJR: 1.053]   [H-I: 47]   [5 followers]  Follow         Hybrid journal (It can contain Open Access articles)    ISSN (Print) 1099-1425 - ISSN (Online) 1094-6136    Published by Springer-Verlag  [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 non-failing interval is accepted, it cannot be aborted and must be processed non-preemptively until completion. For different settings of this problem, we present deterministic and randomized online algorithms and prove lower bounds on the competitive ratio.
PubDate: 2017-01-13
DOI: 10.1007/s10951-016-0506-9

• New strategies for stochastic resource-constrained project scheduling
• Authors: Salim Rostami; Stefan Creemers; Roel Leus
Abstract: Abstract We study the stochastic resource-constrained 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 two-phase local search algorithm is proposed to optimize within the class. Our computational results show that the algorithm has been efficiently tuned toward finding high-quality 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: 2017-01-12
DOI: 10.1007/s10951-016-0505-x

• Online bin stretching with three bins
• Authors: Martin Böhm; Jiří Sgall; Rob van Stee; Pavel Veselý
Abstract: Abstract Online bin stretching is a semi-online 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: 2017-01-11
DOI: 10.1007/s10951-016-0504-y

• 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 energy-efficient 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 pseudo-polynomial time algorithm for agreeable instances.
PubDate: 2016-12-01
DOI: 10.1007/s10951-015-0452-y
Issue No: Vol. 19, No. 6 (2016)

• Co-scheduling algorithms for high-throughput workload execution
• Authors: Guillaume Aupy; Manu Shantharam; Anne Benoit; Yves Robert; Padma Raghavan
Pages: 627 - 640
Abstract: Abstract This paper investigates co-scheduling 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 co-scheduling leads to faster workload completion time (40 % improvement on average over traditional scheduling) and to faster response times (50 % improvement). Hence, co-scheduling increases system throughput and saves energy, leading to significant benefits from both the user and system perspectives.
PubDate: 2016-12-01
DOI: 10.1007/s10951-015-0445-x
Issue No: Vol. 19, No. 6 (2016)

• Optimizing memory allocation for multistage scheduling including setup
times
• Authors: Anne Benoit; Mathias Coqblin; Jean-Marc Nicod; Veronika Rehn-Sonigo
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: 2016-12-01
DOI: 10.1007/s10951-015-0437-x
Issue No: Vol. 19, No. 6 (2016)

• 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: 2016-12-01
DOI: 10.1007/s10951-016-0471-3
Issue No: Vol. 19, No. 6 (2016)

• Scheduling for electricity cost in a smart grid
• Authors: Mihai Burcea; Wing-Kai Hon; Hsiang-Hsuan 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 unit-size. 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: 2016-12-01
DOI: 10.1007/s10951-015-0447-8
Issue No: Vol. 19, No. 6 (2016)

• Normal-form 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 well-known open problem in the theory of preemptive scheduling: Instances consist of in-trees of n unit-execution-time 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 NP-hard problem, but that any significant, but slight simplification leads to tractable problem with a polynomial-time solution. For the above problem, we show that the number of preemptions necessary for optimality need not exceed $$2n-1$$ ; 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 linear-program 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 i-th 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, still-open question of complexity.
PubDate: 2016-12-01
DOI: 10.1007/s10951-015-0446-9
Issue No: Vol. 19, No. 6 (2016)

• 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 two-machine problem is binary NP-hard, and the general case is unary NP-hard. 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: 2016-12-01
DOI: 10.1007/s10951-015-0464-7
Issue No: Vol. 19, No. 6 (2016)

• Scheduling with time-dependent discrepancy times
• Authors: Florian Jaehn; Helmut A. Sedding
Pages: 737 - 757
Abstract: Abstract In time-dependent 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 single-machine scheduling problem with time-dependent 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 branch-and-bound 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 polynomial-time algorithm.
PubDate: 2016-12-01
DOI: 10.1007/s10951-016-0472-2
Issue No: Vol. 19, No. 6 (2016)

• On scheduling with non-increasing 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 non-increasing time slot cost with non-preemptive jobs, we show that the problem can be solved in polynomial-time 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 NP-hard in the strong sense when the time slot cost decreases in an arbitrary way.
PubDate: 2016-12-01
DOI: 10.1007/s10951-015-0462-9
Issue No: Vol. 19, No. 6 (2016)

• Finding optimal tour schedules on transportation paths under extended time
window constraints
• Authors: Stefan Bock
Pages: 527 - 546
Abstract: Abstract This paper addresses time-critical 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 well-known Line-Traveling Repairman problem (Line-TRPTW) is extended into the Line-TRPeTW. The Line-TRPeTW 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 Line-TRPTW/Line-TRPeTW 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 pseudo-polynomial time.
PubDate: 2016-10-01
DOI: 10.1007/s10951-016-0481-1
Issue No: Vol. 19, No. 5 (2016)

• Worst-case 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 flowtime-optimal schedules, called the LD algorithm, has a simple worst-case performance bound: $$\frac{5m-2}{4m-1}$$ , 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: 2016-10-01
DOI: 10.1007/s10951-015-0467-4
Issue No: Vol. 19, No. 5 (2016)

• An analysis of the non-preemptive mixed-criticality match-up scheduling
problem
• Authors: Zdeněk Hanzálek; Tomáš Tunys; Přemysl Šůcha
Pages: 601 - 607
Abstract: Abstract Many applications have a mixed-criticality 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 mixed-criticality 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 off-line, but its on-line 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 non-preemptive mixed-criticality match-up scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3-partition 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: 2016-10-01
DOI: 10.1007/s10951-016-0468-y
Issue No: Vol. 19, No. 5 (2016)

• New challenges in scheduling theory
• Authors: Jacek Blazewicz; Benjamin Moseley; Erwin Pesch; Denis Trystram; Guochuan Zhang
PubDate: 2016-11-30
DOI: 10.1007/s10951-016-0503-z

• Scheduling jobs and maintenance activities subject to job-dependent
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 job-dependent 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 linear-time approximation algorithm with worst-case 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 linear-time approximation algorithm is an improvement over the 5/4 quadratic-time 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 instance-dependent approximation factor and a computational study evaluating the heuristics.
PubDate: 2016-11-12
DOI: 10.1007/s10951-016-0502-0

• 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 worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case 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: 2016-11-11
DOI: 10.1007/s10951-016-0501-1

• Energy-efficient 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 speed-scaling 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 preemptive-nonmigratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-nonmigratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power 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: 2016-10-28
DOI: 10.1007/s10951-016-0500-2

• Scheduling shipments in closed-loop 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 closed-loop 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 short-term 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 low-single-digit optimality gap. In addition, we systematically evaluate the performance gains promised by different sorter layouts.
PubDate: 2016-10-18
DOI: 10.1007/s10951-016-0498-5

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327

Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs