for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 2050 journals)     - ANIMATION AND SIMULATION (30 journals)    - ARTIFICIAL INTELLIGENCE (99 journals)    - AUTOMATION AND ROBOTICS (100 journals)    - CLOUD COMPUTING AND NETWORKS (64 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ENGINEERING (10 journals)    - COMPUTER GAMES (16 journals)    - COMPUTER PROGRAMMING (27 journals)    - COMPUTER SCIENCE (1196 journals)    - COMPUTER SECURITY (46 journals)    - DATA BASE MANAGEMENT (14 journals)    - DATA MINING (32 journals)    - E-BUSINESS (22 journals)    - E-LEARNING (28 journals)    - ELECTRONIC DATA PROCESSING (22 journals)    - IMAGE AND VIDEO PROCESSING (39 journals)    - INFORMATION SYSTEMS (109 journals)    - INTERNET (94 journals)    - SOCIAL WEB (51 journals)    - SOFTWARE (34 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1196 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  [2352 journals]
• Journal of Scheduling (2018)
• Authors: Edmund Burke; Michael Pinedo
Pages: 1 - 1
PubDate: 2018-02-01
DOI: 10.1007/s10951-018-0555-3
Issue No: Vol. 21, No. 1 (2018)

• A survey on how the structure of precedence constraints may change the
complexity class of scheduling problems
• Authors: D. Prot; O. Bellenguez-Morineau
Pages: 3 - 16
Abstract: This survey aims to demonstrate that the structure of precedence constraints plays a tremendous role on the complexity of scheduling problems. Indeed, many problems can be $$\mathcal {NP}$$ -hard when considering general precedence constraints, while they become polynomially solvable for particular precedence constraints. Additionally, the existence of many very exciting challenges in this research area is underlined.
PubDate: 2018-02-01
DOI: 10.1007/s10951-017-0519-z
Issue No: Vol. 21, No. 1 (2018)

• Case mix classification and a benchmark set for surgery scheduling
• Authors: Gréanne Leeftink; Erwin W. Hans
Pages: 17 - 33
Abstract: Numerous benchmark sets exist for combinatorial optimization problems. However, in healthcare scheduling, only a few benchmark sets are known, mainly focused on nurse rostering. One of the most studied topics in the healthcare scheduling literature is surgery scheduling, for which there is no widely used benchmark set. An effective benchmark set should be diverse, reflect the real world, contain large instances, and be extendable. This paper proposes a benchmark set for surgery scheduling algorithms, which satisfies these four criteria. Surgery scheduling instances are characterized by an underlying case mix, which describes the volume and properties of the surgery types. Given a case mix, unlimited random instances can be generated. A complete surgery scheduling benchmark set should encompass the diversity of prevalent case mixes. We therefore propose a case mix classification scheme, which we use to typify both real-life and theoretical case mixes that span the breadth of possible case mix types. Our full benchmark set contains 20,880 instances, with a small benchmark subset of 146 instances. The instances are generated based on real-life case mixes (11 surgical specialties), as well as theoretical instances. The instances were generated using a novel instance generation procedure, which introduces the concept of “instance proximity” to measure the similarity between two instances, and which uses this concept to generate sets of instances that are as diverse as possible.
PubDate: 2018-02-01
DOI: 10.1007/s10951-017-0539-8
Issue No: Vol. 21, No. 1 (2018)

• Energy-efficient scheduling and routing via randomized rounding
• Authors: Evripidis Bampis; Alexander Kononov; Dimitrios Letsios; Giorgio Lucarelli; Maxim Sviridenko
Pages: 35 - 51
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: 2018-02-01
DOI: 10.1007/s10951-016-0500-2
Issue No: Vol. 21, No. 1 (2018)

• Solving a wind turbine maintenance scheduling problem
• Authors: Aurélien Froger; Michel Gendreau; Jorge E. Mendoza; Eric Pinson; Louis-Martin Rousseau
Pages: 53 - 76
Abstract: Driven by climate change mitigation efforts, the wind energy industry has significantly increased in recent years. In this context, it is essential to make its exploitation cost-effective. Maintenance of wind turbines therefore plays an essential role in reducing breakdowns and ensuring high productivity levels. In this paper, we discuss a challenging maintenance scheduling problem rising in the onshore wind power industry. While the research in the field primarily focuses on condition-based maintenance strategies, we aim to address the problem on a short-term horizon considering the wind speed forecast and a fine-grained resource management. The objective is to find a maintenance plan that maximizes the revenue from the electricity production of the turbines while taking into account multiple task execution modes and task-technician assignment constraints. To solve this problem, we propose a constraint programming-based large neighborhood search (CPLNS) approach. We also propose two integer linear programming formulations that we solve using a commercial solver. We report results on randomly generated instances built with input from wind forecasting and maintenance scheduling software companies. The CPLNS shows an average gap of 1.2% with respect to the optimal solutions if known, or to the best upper bounds otherwise. These computational results demonstrate the overall efficiency of the proposed metaheuristic.
PubDate: 2018-02-01
DOI: 10.1007/s10951-017-0513-5
Issue No: Vol. 21, No. 1 (2018)

• Scheduling shared continuous resources on many-cores
• Authors: Ernst Althaus; André Brinkmann; Peter Kling; Friedhelm Meyer auf der Heide; Lars Nagel; Sören Riechers; Jiří Sgall; Tim Süß
Pages: 77 - 92
Abstract: We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement . The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of $$r_j$$ , it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete–continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this article, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include a polynomial-time algorithm for any constant number of processors. Since the running time is infeasible for practical purposes, we also provide more efficient algorithm variants: an optimal algorithm for two processors and a -approximation algorithm for m processors.
PubDate: 2018-02-01
DOI: 10.1007/s10951-017-0518-0
Issue No: Vol. 21, No. 1 (2018)

• Task assignment with start time-dependent processing times for personnel
at check-in counters
• Authors: Emilio Zamorano; Annika Becker; Raik Stolletz
Pages: 93 - 109
Abstract: This paper addresses a task assignment problem encountered by check-in counter personnel at airports. The problem consists of assigning multiskilled agents to a sequence of tasks in check-in counters. Because each task’s ending time is fixed to comply with the flight schedule, its processing time depends on the arrival of the assigned agents. We propose a mixed-integer program and a branch-and-price algorithm to solve this problem. We exploit the problem structure to efficiently formulate the pricing problems and improve computation time. Using real-world data from a German ground-handling agency, we conduct numerical studies to evaluate the performance of the proposed solutions.
PubDate: 2018-02-01
DOI: 10.1007/s10951-017-0523-3
Issue No: Vol. 21, No. 1 (2018)

• Scheduling electric vehicles and locating charging stations on a path
• Authors: Nils Boysen; Dirk Briskorn; Simon Emde
Pages: 111 - 126
Abstract: High hopes are put in electric vehicles to lower global green house gas emissions. From an operational perspective, however, their limited range and the long recharging times add considerable complexity to the decision tasks planning their efficient application. In this context, we treat a problem setting where a single electric vehicle executes transport requests along a straight line, which, for instance, occurs when cranes, automated guided vehicles, or shuttles handle boxes in container terminals. From time to time the vehicle needs to be recharged and, thus, has to visit some charging station also located on the line. We investigate the scheduling of a single electric vehicle, so that the makespan for executing all transport requests is minimized and the vehicle is timely recharged. The solution algorithm developed is then applied to also explore the location planning of charging stations.
PubDate: 2018-02-01
DOI: 10.1007/s10951-017-0538-9
Issue No: Vol. 21, No. 1 (2018)

• Combining two-stage stochastic programming and recoverable robustness to
minimize the number of late jobs in the case of uncertain processing times

• Authors: Marjan van den Akker; Han Hoogeveen; Judith Stoef
Abstract: Minimizing the number of late jobs on a single machine is a classic scheduling problem, which can be used to model the situation that from a set of potential customers, we have to select as many as possible whom we want to serve, while selling no to the other ones. This problem can be solved by Moore–Hodgson’s algorithm, provided that all data are deterministic. We consider a stochastic variant of this problem, where we assume that there is a small probability that the processing times differ from their standard values as a result of some kind of disturbance. When such a disturbance occurs, then we must apply some recovery action to make the solution feasible again. This leads us to the area of recoverable robustness, which handles this uncertainty by modeling each possible disturbance as a scenario; in each scenario, the initial solution must then be made feasible by applying a given, simple recovery algorithm to it. Since we cannot accept previously rejected customers, our only option is to reject customers that would have been served in the undisturbed case. Our problem therefore becomes to find a solution for the undisturbed case together with a feasible recovery to every possible disturbance. Our goal hereby is to maximize the expected number of served customers; we assume here that we know the probability that a given scenario occurs. In this respect, our problem falls outside the area of the ‘standard’ recoverable robustness, which contains the worst-case recovery cost as a component of the objective. Therefore, we consider our approach as a combination of two-stage stochastic programming and recoverable robustness. We show that this problem is $$\mathcal{NP}$$ -hard in the ordinary sense even if there is only one scenario, and we present some sufficient conditions that allow us to find a part of the optimal solution in polynomial time. We further evaluate several solution methods to find an optimal solution, among which are dynamic programming, branch-and-bound, and branch-and-price.
PubDate: 2018-02-19
DOI: 10.1007/s10951-018-0559-z

• An efficient train scheduling algorithm on a single-track railway system
• Authors: Xiaoming Xu; Keping Li; Lixing Yang; Ziyou Gao
Abstract: Since scheduling trains on a single-track railway line is an NP-hard problem, this paper proposes an efficient heuristic algorithm based on a train movement simulation method to search for the near-optimal train timetables within the acceptable computational time. Specifically, the time–space statuses of trains in the railway system are firstly divided into three categories, including dwelling at a station, waiting at a station and traveling on a segment. A check algorithm is particularly proposed to guarantee the feasibility of transition among different statuses in which each status transition is defined as a discrete event. Several detailed operation rules are also developed to clarify the scheduling procedure in some special cases. We then design an iterative discrete event simulation-based train scheduling method, namely, train status transition approach (TSTA), in which the status transition check algorithm and operation rules are incorporated. Finally, we implement some extensive experiments by using randomly generated data set to show the effectiveness and efficiency of the proposed TSTA.
PubDate: 2018-02-17
DOI: 10.1007/s10951-018-0558-0

• 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

• 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

• 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

• 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

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