for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 1992 journals)     - ANIMATION AND SIMULATION (29 journals)    - ARTIFICIAL INTELLIGENCE (98 journals)    - AUTOMATION AND ROBOTICS (98 journals)    - CLOUD COMPUTING AND NETWORKS (60 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ENGINEERING (9 journals)    - COMPUTER GAMES (16 journals)    - COMPUTER PROGRAMMING (24 journals)    - COMPUTER SCIENCE (1159 journals)    - COMPUTER SECURITY (45 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 (105 journals)    - INTERNET (92 journals)    - SOCIAL WEB (50 journals)    - SOFTWARE (34 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1159 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  [2354 journals]
• 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)

• Reordering buffer management with advice
• Authors: Anna Adamaszek; Marc P. Renault; Adi Rosén; Rob van Stee
Pages: 423 - 442
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)

• Scheduling cleaning activities on trains by minimizing idle times
• Authors: Enrico Bartolini; Mauro Dell’Amico; Manuel Iori
Pages: 493 - 506
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)

• 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

• An implicit model for multi-activity shift scheduling problems
• Authors: Sana Dahmen; Monia Rekik; François Soumis
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: 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: 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: 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: 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