for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 2002 journals)     - ANIMATION AND SIMULATION (29 journals)    - ARTIFICIAL INTELLIGENCE (99 journals)    - AUTOMATION AND ROBOTICS (100 journals)    - CLOUD COMPUTING AND NETWORKS (63 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ENGINEERING (9 journals)    - COMPUTER GAMES (16 journals)    - COMPUTER PROGRAMMING (24 journals)    - COMPUTER SCIENCE (1160 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 (40 journals)    - INFORMATION SYSTEMS (107 journals)    - INTERNET (91 journals)    - SOCIAL WEB (50 journals)    - SOFTWARE (34 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1160 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]
• Reordering buffer management with advice
• Authors: Anna Adamaszek; Marc P. Renault; Adi Rosén; Rob van Stee
Pages: 423 - 442
Abstract: Abstract In the reordering buffer management problem, a sequence of colored items arrives at a service station to be processed. Each color change between two consecutively processed items generates some cost. A reordering buffer of capacity k items can be used to preprocess the input sequence in order to decrease the number of color changes. The goal is to find a scheduling strategy that, using the reordering buffer, minimizes the number of color changes in the given sequence of items. We consider the problem in the setting of online computation with advice. In this model, the color of an item becomes known only at the time when the item enters the reordering buffer. Additionally, together with each item entering the buffer, we get a fixed number of advice bits, which can be seen as information about the future or as information about an optimal solution (or an approximation thereof) for the whole input sequence. We show that for any $$\varepsilon > 0$$ there is a $$(1+\varepsilon )$$ -competitive algorithm for the problem which uses only a constant (depending on $$\varepsilon$$ ) number of advice bits per input item. This also immediately implies a $$(1+\varepsilon )$$ -approximation algorithm which has $$2^{O(n\log 1/\varepsilon )}$$ running time (this should be compared to the trivial optimal algorithm which has a running time of $$k^{O(n)}$$ ). We complement the above result by presenting a lower bound of $$\varOmega (\log k)$$ bits of advice per request for any 1-competitive algorithm.
PubDate: 2017-10-01
DOI: 10.1007/s10951-016-0487-8
Issue No: Vol. 20, No. 5 (2017)

• Online interval scheduling with a bounded number of failures
• Authors: Marco Bender; Clemens Thielen; Stephan Westphal
Pages: 443 - 457
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-10-01
DOI: 10.1007/s10951-016-0506-9
Issue No: Vol. 20, No. 5 (2017)

• Mathematical models for the berth allocation problem in dry bulk terminals
• Authors: Andreas T. Ernst; Ceyda Oğuz; Gaurav Singh; Gita Taherkhani
Pages: 459 - 473
Abstract: Abstract Port terminals processing large cargo vessels play an important role in bulk material supply chains. This paper addresses the question of how to allocate vessels to a location on a berth and the sequence in which the vessels should be processed in order to minimize delays. An important consideration in the berth allocation is the presence of tidal constraints that limit the departure of fully loaded vessels from the terminal. We show how the berth allocation problem can be modeled as an integer program and discuss a number of ways to tighten the formulation in order to make it computationally tractable. In addition, a two-phase method is developed for solving these problems. Empirical computational results demonstrate an order of magnitude improvement in performance. The two new approaches can solve significantly larger instances, producing faster solutions for small instances and much tighter bounds for large instances.
PubDate: 2017-10-01
DOI: 10.1007/s10951-017-0510-8
Issue No: Vol. 20, No. 5 (2017)

• Finding an optimal Nash equilibrium to the multi-agent project scheduling
problem
• Authors: Cyril Briand; Sandra Ulrich Ngueveu; Přemysl Šůcha
Pages: 475 - 491
Abstract: Abstract Large projects often involve a set of contractors, each in charge of a part of the project. In this paper, we assume that every contractor is self-interested and can control the duration of his/her activities, which can be shortened up to an incompressible limit, by gathering extra resources at a given cost. In this context, the resulting project makespan depends on all the contractors’ decisions. The customer of the project is interested in a short project makespan and offers a reward, proportional to the project makespan reduction, to be shared by the contractors. In practice, either the reward sharing policy results from an upfront agreement or payments are freely allocated by the customer. Each contractor is only interested in the maximization of his/her profit and behaves accordingly. This paper addresses the problem of finding a Nash equilibrium and a sharing policy that minimize the project makespan. The aim is to help the customer to determine the duration of the activities and the reward sharing policy such that no agent has an incentive to unilaterally deviate from this solution. We show that this problem is NP-hard and how it can be modeled and solved by mixed integer linear programming. Computational analysis on large instances proves the effectiveness of our approach. Based on an empirical investigation of the influence of reward sharing policies on the project makespan, the paper provides new insight into how a project’s customer should offer rewards to the contractors.
PubDate: 2017-10-01
DOI: 10.1007/s10951-017-0516-2
Issue No: Vol. 20, No. 5 (2017)

• Scheduling cleaning activities on trains by minimizing idle times
• Authors: Enrico Bartolini; Mauro Dell’Amico; Manuel Iori
Pages: 493 - 506
Abstract: Abstract We consider a workforce scheduling problem which consists of determining optimal working shifts for cleaning personnel at a rail station. Trains arrive and depart according to a specified schedule and require a given amount of cleaning time from the personnel before their departure from the station. Working shifts must specify a sequence of trains to be cleaned by a worker together with corresponding cleaning times and are subject to contract regulations which impose both a minimum and a maximum duration of the shift. We model the problem as a mixed-integer program with a pseudo-polynomial number of variables and propose an exponentially sized reformulation obtained through Dantzig–Wolfe reformulation. The reformulation is strengthened by valid inequalities and used to compute lower bounds on the optimal cost. A heuristic algorithm based on column generation and variable fixing is then proposed and computationally evaluated on both a set of instances derived from real data and a larger set of randomly generated ones. The reported computational results show that the algorithm provides solutions very close to the optimal ones within 1 h of computing time.
PubDate: 2017-10-01
DOI: 10.1007/s10951-017-0517-1
Issue No: Vol. 20, No. 5 (2017)

• Crane scheduling in railway yards: an analysis of computational complexity
• Authors: Konrad Stephan; Nils Boysen
Pages: 507 - 526
Abstract: Abstract An efficient container transfer in railway yards is an important matter to increase the attraction of rail-bound freight transport. Therefore, the scheduling of gantry cranes transferring containers between freight trains and trucks or among trains received a lot of attention in the recent years. This paper contributes to this stream of research by investigating the computational complexity of crane scheduling in these yards. Scheduling the transfer of a given set of containers by a single crane equals the (asymmetric) traveling salesman problem in its path-version. In railway yards, however, all container positions are located along parallel lines, i.e., tracks, and we face special distance metrics, so that only specially structured problem instances arise. We classify important problem settings by differentiating the transshipment direction, parking policy, and distance metric. This way, we derive problem variants being solvable to optimality in polynomial time, whereas other cases are shown to be NP-hard.
PubDate: 2017-10-01
DOI: 10.1007/s10951-017-0520-6
Issue No: Vol. 20, No. 5 (2017)

• Two-agent flowshop scheduling to maximize the weighted number of
just-in-time jobs
• Authors: Yunqiang Yin; T. C. E. Cheng; Du-Juan Wang; Chin-Chia Wu
Pages: 313 - 335
Abstract: Abstract We consider the scheduling problem in which two agents (agents A and B), each having its own job set (containing the A-jobs and B-jobs, respectively), compete to process their own jobs in a two-machine flowshop. Each agent wants to maximize a certain criterion depending on the completion times of its jobs only. Specifically, agent A desires to maximize either the weighted number of just-in-time (JIT) A-jobs that are completed exactly on their due dates or the maximum weight of the JIT A-jobs, while agent B wishes to maximize the weighted number of JIT B-jobs. Evidently four optimization problems can be formulated by treating the two agents’ criteria as objectives and constraints of the corresponding optimization problems. We focus on the problem of finding the Pareto-optimal schedules and present a bicriterion analysis of the problem. Solving this problem also solves the other three problems of bicriterion scheduling as a by-product. We show that the problems under consideration are either polynomially or pseudo-polynomially solvable. In addition, for each pseudo-polynomial-time solution algorithm, we show how to convert it into a two-dimensional fully polynomial-time approximation scheme for determining an approximate Pareto-optimal schedule. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.
PubDate: 2017-08-01
DOI: 10.1007/s10951-017-0511-7
Issue No: Vol. 20, No. 4 (2017)

• Non-preemptive buffer management for latency sensitive packets
• Authors: Moran Feldman; Joseph (Seffi) Naor
Pages: 337 - 353
Abstract: Abstract The delivery of latency sensitive packets is a crucial issue in real-time applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a non-preemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a real-valued model, where any value over 1 is allowed, and an integral-valued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the real-valued model, we give a randomized 4-competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of $$\phi ^3 - {\varepsilon }\approx 4.236$$ , almost matching the previously known 4.24-competitive algorithm. For the integral-valued model, we describe a deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).
PubDate: 2017-08-01
DOI: 10.1007/s10951-016-0474-0
Issue No: Vol. 20, No. 4 (2017)

• An exact algorithm for parallel machine scheduling with conflicts
• Authors: Daniel Kowalczyk; Roel Leus
Pages: 355 - 372
Abstract: Abstract We consider an extension of classic parallel machine scheduling where a set of jobs is scheduled on identical parallel machines and an undirected conflict graph is part of the input. Each node in the graph represents a job, and an edge implies that its two jobs are conflicting, meaning that they cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time (makespan) is minimized. We present an exact algorithm based on branch and price that combines methods from bin packing, scheduling, and graph coloring, with appropriate modifications. The algorithm has a good computational performance even for parallel machine scheduling without conflicting jobs.
PubDate: 2017-08-01
DOI: 10.1007/s10951-016-0482-0
Issue No: Vol. 20, No. 4 (2017)

• An exact extended formulation for the unrelated parallel machine total
weighted completion time problem
• Authors: Kerem Bülbül; Halil Şen
Pages: 373 - 389
Abstract: Abstract The plethora of research on $$\mathcal {NP}$$ -hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted to the identical parallel machine scheduling environment. In this context, the main contribution of this work is to recognize and prove that a particular preemptive relaxation for the problem of minimizing the total weighted completion time (TWCT) on a set of unrelated parallel machines naturally admits a non-preemptive optimal solution and gives rise to an exact mixed integer linear programming formulation of the problem. Furthermore, we exploit the structural properties of TWCT and attain a very fast and scalable exact Benders decomposition-based algorithm for solving this formulation. Computationally, our approach holds great promise and may even be embedded into iterative algorithms for more complex shop scheduling problems as instances with up to 1000 jobs and 8 machines are solved to optimality within a few seconds.
PubDate: 2017-08-01
DOI: 10.1007/s10951-016-0485-x
Issue No: Vol. 20, No. 4 (2017)

• An implicit model for multi-activity shift scheduling problems
• Authors: Sana Dahmen; Monia Rekik; François Soumis
Abstract: Abstract We consider a multi-activity shift scheduling problem where the objective is to construct anonymous multi-activity shifts that respect union rules, satisfy the demand and minimize workforce costs. An implicit approach using adapted forward and backward constraints is proposed that integrates both the shift construction and the activity assignment problems. Our computational study shows that using the branch-and-bound procedure of CPLEX 12.6 on the proposed implicit model yields optimal solutions in relatively short times for environments including up to 2970 millions of explicit shifts. Our implicit model is compared to the grammar-based implicit model proposed by Côté et al. (Manag Sci 57(1):151–163, 2011b) on a large set of instances. The results prove that both implicit models have their strengths and weaknesses and are more or less efficient depending on the scheduling environment.
PubDate: 2017-10-11
DOI: 10.1007/s10951-017-0544-y

• Single-machine scheduling with workload-dependent tool change durations
and equal processing time jobs to minimize total completion time
• Authors: Zhijun Xu; Dehua Xu
Abstract: Abstract We consider a single-machine tool change scheduling problem where tool change durations are workload-dependent. The processing times of all the jobs are the same. The objective is to determine the number of tool change activities, the start time and the completion time of each tool change activity jointly and schedule all the jobs to the machine such that the total completion time of the jobs is minimized. For the case where the tool change duration function is concave, we present a linear time optimal algorithm. For the case where the tool change duration function is convex, we convert it into a convex integer quadratic programming problem with fixed dimension and then propose two polynomial time algorithms for it. We also study some special cases for which optimal schedules can be obtained directly. For the case where the tool change duration function is linear, we present all the optimal schedules.
PubDate: 2017-10-05
DOI: 10.1007/s10951-017-0543-z

• Two-stage hybrid flowshop scheduling with simultaneous processing machines
• Authors: Bailin Wang; Kai Huang; Tieke Li
Abstract: Abstract Simultaneous processing machines, common in processing industries such as steel and food production, can process several jobs simultaneously in the first-in, first-out manner. However, they are often highly energy-consuming. In this paper, we study a new two-stage hybrid flowshop scheduling problem, with simultaneous processing machines at the first stage and a single no-idle machine with predetermined job sequence at the second stage. A mixed integer programming model is proposed with the objective of minimizing the total processing time to reduce energy consumption and improve production efficiency. We give a sufficient and necessary condition to construct feasible sequencing solutions and present an effective approach to calculate the time variables for a feasible sequencing solution. Based on these results, we design a list scheduling heuristic algorithm and its improvement. Both heuristics can find an optimal solution under certain conditions with complexity O(nlogn), where n is the number of jobs. Our experiments verify the efficiency of these heuristics compared with classical heuristics in the literature and investigate the impacts of problem size and processing times.
PubDate: 2017-10-04
DOI: 10.1007/s10951-017-0545-x

• Integrated production and outbound distribution scheduling problems with
• Authors: Liang-Liang Fu; Mohamed Ali Aloulou; Christian Artigues
Abstract: Abstract In this paper, we study an integrated production and outbound distribution scheduling model with one manufacturer and one customer. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to the customer. Each job has a release date and a delivery deadline. The objective of the problem is to issue a feasible integrated production and distribution schedule minimizing the transportation cost subject to the production release dates and delivery deadline constraints. We consider three problems with different ways how a job can be produced and delivered: non-splittable production and delivery (NSP–NSD) problem, splittable production and non-splittable delivery problem and splittable production and delivery problem. We provide polynomial-time algorithms that solve special cases of the problem. One of these algorithms allows us to compute a lower bound for the NP-hard problem NSP–NSD, which we use in a branch-and-bound (B&B) algorithm to solve problem NSP–NSD. The computational results show that the B&B algorithm outperforms a MILP formulation of the problem implemented on a commercial solver.
PubDate: 2017-10-04
DOI: 10.1007/s10951-017-0542-0

• Complexity results for an integrated single machine scheduling and
outbound delivery problem with fixed sequence
• Abstract: 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: 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

• Case mix classification and a benchmark set for surgery scheduling
• Authors: Gréanne Leeftink; Erwin W. Hans
Abstract: 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: 2017-09-05
DOI: 10.1007/s10951-017-0539-8

• Scheduling electric vehicles and locating charging stations on a path
• Authors: Nils Boysen; Dirk Briskorn; Simon Emde
Abstract: 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: 2017-08-24
DOI: 10.1007/s10951-017-0538-9

• Offline first-fit decreasing height scheduling of power loads
• Authors: Anshu Ranjan; Pramod Khargonekar; Sartaj Sahni
Abstract: Abstract In this paper, we consider the problem of scheduling energy consumption loads in the setting of smart electric grids. Each load is characterized as a “job” by a start (arrival) time and a deadline by which a certain amount of electric energy must be delivered to the load. A job may be preemptable, i. e. it can be interrupted or non-preemptable. Specifically, we focus on scheduling a mixture of preemptable and non-preemptable jobs with the same arrival time and deadline with the goal of minimizing the peak power. We study and modify the first-fit decreasing height algorithm of the strip packing problem for this purpose. We prove its asymptotic performance bound: $$1.7 OPT + 1$$ and its tightness. The heuristic results in at most one preemption per job, and it can be implemented with $$O(n \log n + nq)$$ time complexity where q is the number of $$non-preemptable$$ jobs.
PubDate: 2017-06-21
DOI: 10.1007/s10951-017-0528-y

• A neighborhood for complex job shop scheduling problems with regular
objectives
• Authors: Reinhard Bürgy
Abstract: Abstract Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer limitations, and have pursued objectives that are more practically relevant than the makespan, such as total flow time and total weighted tardiness. However, most proposed solution approaches are tailored to the specific scheduling problem studied and are not applicable to more general settings. This article proposes a neighborhood that can be applied for a large class of job shop scheduling problems with regular objectives. Feasible neighbor solutions are generated by extracting a job from a given solution and reinserting it into a neighbor position. This neighbor generation in a sense extends the simple swapping of critical arcs, a mechanism that is widely used in the classical job shop but that is not applicable in more complex job shop problems. The neighborhood is embedded in a tabu search, and its performance is evaluated with an extensive experimental study using three standard job shop scheduling problems: the (classical) job shop, the job shop with sequence-dependent setup times, and the blocking job shop, combined with the following five regular objectives: makespan, total flow time, total squared flow time, total tardiness, and total weighted tardiness. The obtained results support the validity of the approach.
PubDate: 2017-06-14
DOI: 10.1007/s10951-017-0532-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