for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 2011 journals)     - ANIMATION AND SIMULATION (30 journals)    - ARTIFICIAL INTELLIGENCE (98 journals)    - AUTOMATION AND ROBOTICS (98 journals)    - CLOUD COMPUTING AND NETWORKS (61 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ENGINEERING (9 journals)    - COMPUTER GAMES (16 journals)    - COMPUTER PROGRAMMING (24 journals)    - COMPUTER SCIENCE (1172 journals)    - COMPUTER SECURITY (46 journals)    - DATA BASE MANAGEMENT (13 journals)    - DATA MINING (32 journals)    - E-BUSINESS (22 journals)    - E-LEARNING (29 journals)    - ELECTRONIC DATA PROCESSING (21 journals)    - IMAGE AND VIDEO PROCESSING (39 journals)    - INFORMATION SYSTEMS (108 journals)    - INTERNET (92 journals)    - SOCIAL WEB (50 journals)    - SOFTWARE (34 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1172 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  [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: 2018-02-02
DOI: 10.1007/s10951-018-0556-2

• Minimizing worst-case and average-case makespan over scenarios
• Authors: Esteban Feuerstein; Alberto Marchetti-Spaccamela; 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: 2017-12-01
DOI: 10.1007/s10951-016-0484-y
Issue No: Vol. 20, No. 6 (2017)

• 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 two-machine 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 NP-hard 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: 2017-12-01
DOI: 10.1007/s10951-016-0490-0
Issue No: Vol. 20, No. 6 (2017)

• Single machine scheduling with a generalized job-dependent 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 half-product, which allows us to develop a fully polynomial-time approximation scheme with the best possible running time.
PubDate: 2017-12-01
DOI: 10.1007/s10951-016-0497-6
Issue No: Vol. 20, No. 6 (2017)

• 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 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: 2017-12-01
DOI: 10.1007/s10951-016-0501-1
Issue No: Vol. 20, No. 6 (2017)

• 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 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-12-01
DOI: 10.1007/s10951-016-0504-y
Issue No: Vol. 20, No. 6 (2017)

• Scheduling multipacket frames with frame deadlines
• Authors: Łukasz Jeż; Yishay Mansour; Boaz Patt-Shamir
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 constant-competitive 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 polylog-competitive algorithms for general instances with slack and bounded jitter.
PubDate: 2017-12-01
DOI: 10.1007/s10951-017-0522-4
Issue No: Vol. 20, No. 6 (2017)

• Staff and machine shift scheduling in a German potash mine
• Authors: Marco Schulze; Jürgen Zimmermann
Pages: 635 - 656
Abstract: This paper addresses a short-term 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 mining-specific 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 multi-start algorithm. In a computational study, we conduct experiments on random as well as real-world instances.
PubDate: 2017-12-01
DOI: 10.1007/s10951-017-0527-z
Issue No: Vol. 20, No. 6 (2017)

• 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 3-approximation (and this bound is tight) and we further improve this to a 2-approximation via LP rounding techniques. Our second contribution is for the non-preemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NP-hard, 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 4-approximation is known for this problem. We develop a new combinatorial algorithm that gives a 3-approximation. 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 2-approximate.
PubDate: 2017-12-01
DOI: 10.1007/s10951-017-0531-3
Issue No: Vol. 20, No. 6 (2017)

• A two-stage stochastic program for multi-shift, multi-analyst, workforce
optimization with multiple on-call 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 on-call 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 two-stage stochastic program and solve it with a column-generation-based 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: 2017-12-22
DOI: 10.1007/s10951-017-0554-9

• 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 search-based 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 high-quality 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: 2017-12-15
DOI: 10.1007/s10951-017-0549-6

• The proactive and reactive resource-constrained project scheduling problem
• Authors: Morteza Davari; Erik Demeulemeester
Abstract: Uncertainty has become an inevitable aspect of project scheduling. We study the resource-constrained 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 proactive-and-reactive policies (PR-policies). We discuss that PR-policies 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 PR-policies. 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: 2017-12-13
DOI: 10.1007/s10951-017-0553-x

• Models and algorithms for energy-efficient 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 single-machine 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 Pareto-optimal solution.
PubDate: 2017-12-12
DOI: 10.1007/s10951-017-0552-y

• 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: 2017-12-11
DOI: 10.1007/s10951-017-0551-z

• 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 NP-hard 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 fixed-parameter tractable for some natural parameters. Our main tool is n-fold 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 fixed-parameter 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: 2017-11-15
DOI: 10.1007/s10951-017-0550-0

• 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: 2017-11-10
DOI: 10.1007/s10951-017-0548-7

• The Current state of bounds on benchmark instances of the job-shop
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: 2017-10-28
DOI: 10.1007/s10951-017-0547-8

• An algorithm for multi-agent scheduling to minimize the makespan on m
parallel machines
• Authors: Manzhan Gu; Jinwei Gu; Xiwen Lu
Abstract: This paper considers a multi-agent scheduling problem, in which each agent has a set of non-preemptive 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: 2017-10-20
DOI: 10.1007/s10951-017-0546-9

• 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 NP-hardness of the general problem is established, and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NP-hardness proofs and polynomial time algorithms are given. Finally, a fixed-parameter tractability result is given.
PubDate: 2017-09-08
DOI: 10.1007/s10951-017-0540-2

• 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 1-completed load competitiveness properties of deterministic scheduling algorithms under worst-case 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 1-completed-load competitiveness when the speedup is over the threshold. This also proves that the threshold identified is also sufficient for competitiveness.
PubDate: 2017-09-07
DOI: 10.1007/s10951-017-0541-1

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