for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 1964 journals)     - ANIMATION AND SIMULATION (29 journals)    - ARTIFICIAL INTELLIGENCE (98 journals)    - AUTOMATION AND ROBOTICS (96 journals)    - CLOUD COMPUTING AND NETWORKS (64 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ENGINEERING (10 journals)    - COMPUTER GAMES (15 journals)    - COMPUTER PROGRAMMING (23 journals)    - COMPUTER SCIENCE (1143 journals)    - COMPUTER SECURITY (44 journals)    - DATA BASE MANAGEMENT (12 journals)    - DATA MINING (32 journals)    - E-BUSINESS (22 journals)    - E-LEARNING (28 journals)    - ELECTRONIC DATA PROCESSING (21 journals)    - IMAGE AND VIDEO PROCESSING (41 journals)    - INFORMATION SYSTEMS (97 journals)    - INTERNET (90 journals)    - SOCIAL WEB (48 journals)    - SOFTWARE (34 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1143 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  [2336 journals]
• Finding optimal tour schedules on transportation paths under extended time
window constraints
• Authors: Stefan Bock
Pages: 527 - 546
Abstract: Abstract This paper addresses time-critical routing on a given path under release dates and deadline restrictions, while the minimization of the total weighted completion time is pursued. Since there may be destinations with flexible picking area resources that enable a delivery of goods before the defined release date at no additional costs, the well-known Line-Traveling Repairman problem (Line-TRPTW) is extended into the Line-TRPeTW. The Line-TRPeTW has various practical applications, such as, for example, the tour planning of an inland container ship along a river or that of a vehicle along a coastline. Although the feasibility variant of the Line-TRPTW/Line-TRPeTW is known to be strongly $${\mathcal {NP}}$$ -hard, a first practically applicable Branch&Bound procedure is generated. By making use of different dominance rules and lower bounds, a comprehensive computational study proves that instances comprising up to 200 requests and locations are solved to optimality in reasonable time. Moreover, the paper analyzes the complexity of the simpler variant with relaxed release dates at all customer locations. This relaxed variant provides tight lower bounds. Furthermore, the complexity analysis shows that the relaxed problem variant is binary $${\mathcal {NP}}$$ -hard even if deadlines are ignored, but can be efficiently solved by a specific Dynamic Programming approach that runs in pseudo-polynomial time.
PubDate: 2016-10-01
DOI: 10.1007/s10951-016-0481-1
Issue No: Vol. 19, No. 5 (2016)

• Worst-case performance analysis of some approximation algorithms for
minimizing makespan and flowtime
• Authors: Peruvemba Sundaram Ravi; Levent Tunçel; Michael Huang
Pages: 547 - 561
Abstract: Abstract In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime-optimal schedules, called the LD algorithm, has a simple worst-case performance bound: $$\frac{5m-2}{4m-1}$$ , where m is the number of machines. We study the structure of potential minimal counterexamples to this conjecture, provide some new tools and techniques for the analysis of such algorithms, and prove that to verify the conjecture, it suffices to analyze the following case: for every $$m \ge 4$$ , $$n \in \{4m, 5m\}$$ , where n is the number of jobs.
PubDate: 2016-10-01
DOI: 10.1007/s10951-015-0467-4
Issue No: Vol. 19, No. 5 (2016)

• A reclaimer scheduling problem arising in coal stockyard management
• Authors: Enrico Angelelli; Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
Pages: 563 - 582
Abstract: We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm.
PubDate: 2016-10-01
DOI: 10.1007/s10951-015-0436-y
Issue No: Vol. 19, No. 5 (2016)

• Scheduling parallel-machine batch operations to maximize on-time delivery
performance
• Authors: Shubin Xu; James C. Bean
Pages: 583 - 600
Abstract: Abstract In this paper we study the problem of minimizing total weighted tardiness, a proxy for maximizing on-time delivery performance, on parallel nonidentical batch processing machines. We first formulate the (primal) problem as a nonlinear integer programming model. We then show that the primal problem can be solved exactly by solving a corresponding dual problem with a nonlinear relaxation. Since both the primal and the dual problems are NP-hard, we use genetic algorithms, based on random keys and multiple choice encodings, to heuristically solve them. We find that the genetic algorithms consistently outperform a standard mathematical programming package in terms of solution quality and computation time. We also compare the smaller problem instances to a breadth-first tree search algorithm that gives evidence of the quality of the solutions.
PubDate: 2016-10-01
DOI: 10.1007/s10951-015-0449-6
Issue No: Vol. 19, No. 5 (2016)

• An analysis of the non-preemptive mixed-criticality match-up scheduling
problem
• Authors: Zdeněk Hanzálek; Tomáš Tunys; Přemysl Šůcha
Pages: 601 - 607
Abstract: Abstract Many applications have a mixed-criticality nature. They contain tasks with a different criticality, meaning that a task with a lower criticality can be skipped if a task with a higher criticality needs more time to be executed. This paper deals with a mixed-criticality scheduling problem where each task has a criticality given by a positive integer number. The exact processing time of the task is not known. Instead, we use different upper bounds of the processing time for different criticality levels of the schedule. A schedule with different criticality levels is generated off-line, but its on-line execution switches among the criticality levels depending on the actual values of the processing times. The advantage is that after the transient prolongation of a higher criticality task, the system is able to match up with the schedule on a lower criticality level. While using this model, we achieve significant schedule efficiency (assuming that the prolongation of the higher criticality task rarely occurs), and at the same time, we are able to grant a sufficient amount of time to higher criticality tasks (in such cases, some of the lower criticality tasks may be skipped). This paper shows a motivation for the non-preemptive mixed-criticality match-up scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3-partition problem, we prove the problem to be $$\mathcal {NP}$$ -hard in the strong sense even when the release dates and deadlines are dropped and only two criticality levels are considered.
PubDate: 2016-10-01
DOI: 10.1007/s10951-016-0468-y
Issue No: Vol. 19, No. 5 (2016)

• High-multiplicity scheduling on one machine with forbidden start and
completion times
• Authors: Michaël Gabay; Christophe Rapine; Nadia Brauner
Pages: 609 - 616
Abstract: Abstract We are interested in a single machine scheduling problem where jobs can neither start nor end on some specified instants, and the aim is to minimize the makespan. This problem models the situation where an additional resource, subject to unavailability constraints, is required to start and to finish a job. We consider in this paper the high-multiplicity version of the problem, when the input is given using a compact encoding. We present a polynomial time algorithm for large diversity instances (when the number of different processing times is greater than the number of forbidden instants). We also show that this problem is fixed-parameter tractable when the number of forbidden instants is fixed, regardless of jobs characteristics.
PubDate: 2016-10-01
DOI: 10.1007/s10951-016-0475-z
Issue No: Vol. 19, No. 5 (2016)

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

• Scheduling jobs and maintenance activities subject to job-dependent
machine deteriorations
• Authors: Liliana Grigoriu; Dirk Briskorn
Abstract: Abstract This paper considers machine scheduling that integrates machine deterioration caused by jobs and, consequently, maintenance activities. The maintenance state of the machine is represented by a maintenance level which drops by a certain, possibly job-dependent amount while jobs are processed. A maintenance level of less than zero is associated with the machine’s breakdown and is therefore forbidden. Hence, maintenance activities that raise the maintenance level may become necessary and have to be scheduled additionally. We consider the objective to minimize the makespan throughout the paper. For the single machine case, we provide a linear-time approximation algorithm with worst-case a bound of 5/4, and comment on how an FPTAS from previous literature can be employed to apply to our problem. Due to problem similarity, these results also apply to the minimum subset sum problem, and the 5/4 linear-time approximation algorithm is an improvement over the 5/4 quadratic-time approximation algorithm of Güntzer and Jungnickel. For the general problem with multiple machines, we provide approximability results, two fast heuristics, an approximation algorithm with an instance-dependent approximation factor and a computational study evaluating the heuristics.
PubDate: 2016-11-12
DOI: 10.1007/s10951-016-0502-0

• Approximation for scheduling on uniform nonsimultaneous parallel machines
• Authors: Liliana Grigoriu; Donald K. Friesen
Abstract: Abstract We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within $$\sqrt{6}/2$$ times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines.
PubDate: 2016-11-11
DOI: 10.1007/s10951-016-0501-1

• Energy-efficient scheduling and routing via randomized rounding
• Authors: Evripidis Bampis; Alexander Kononov; Dimitrios Letsios; Giorgio Lucarelli; Maxim Sviridenko
Abstract: Abstract We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-nonmigratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-nonmigratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
PubDate: 2016-10-28
DOI: 10.1007/s10951-016-0500-2

• Scheduling shipments in closed-loop sortation conveyors
• Authors: Dirk Briskorn; Simon Emde; Nils Boysen
Abstract: Abstract At the very core of most automated sorting systems— for example, at airports for baggage handling and in parcel distribution centers for sorting mail—we find closed-loop tilt tray sortation conveyors. In such a system, trays are loaded with cargo as they pass through loading stations, and are later tilted upon reaching the outbound container dedicated to a shipment’s destination. This paper addresses the question of whether the simple decision rules typically applied in the real world when deciding which parcel should be loaded onto what tray are, indeed, a good choice. We formulate a short-term deterministic scheduling problem where a finite set of shipments must be loaded onto trays such that the makespan is minimized. We consider different levels of flexibility in how to arrange shipments on the feeding conveyors, and distinguish between unidirectional and bidirectional systems. In a comprehensive computational study, we compare these sophisticated optimization procedures with widespread rules of thumb, and find that the latter perform surprisingly well. For almost all problem settings, some priority rule can be identified which leads to a low-single-digit optimality gap. In addition, we systematically evaluate the performance gains promised by different sorter layouts.
PubDate: 2016-10-18
DOI: 10.1007/s10951-016-0498-5

• A hybrid multi-objective immune algorithm for predictive and reactive
scheduling
• Authors: Iwona Paprocka; Bożena Skołud
Abstract: Abstract The high productivity of a production process has a major impact on the reduction of the production cost and on a quick response to changing demands. Information about a failure-free machine operation time obtained in advance allows the users to plan preventive maintenance in order to keep the machine in a good operational condition. The introduction of maintenance work into a schedule reduces the frequency of unpredicted breaks caused by machine failures. It also results in higher productivity and in-time production. The foregoing of this constitutes the main idea of the predictive scheduling method proposed in the paper. Rescheduling of disrupted operations, with a minimal impact on the stability and robustness of a schedule, is the main idea of the reactive scheduling method proposed. The first objective of the paper is to present a hybrid multi-objective immune algorithm (H-MOIA) aided by heuristics: a minimal impact of disrupted operation on the schedule (MIDOS) for predictive scheduling and a minimal impact of rescheduled operation on the schedule (MIROS) for reactive scheduling. The second objective is to compare the H-MOIA with various methods for predictive and reactive scheduling. The H-MOIA + MIDOS is compared to two algorithms, identified in reference publications: (1) an algorithm based on priority rules: the least flexible job first (LFJ) and the longest processing time (LPT) (2) an Average Slack Method. The H-MOIA + MIROS is compared to: (1) an algorithm based on priority rules: the LFJ and LPT and (2) Shifted Gap-Reduction. This paper presents the research results and computer simulations.
PubDate: 2016-09-26
DOI: 10.1007/s10951-016-0494-9

• Scheduling reclaimers serving a stock pad at a coal terminal
• Authors: Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
Abstract: We study a variant of an abstract scheduling problem inspired by the management of reclaimers in the stockyard of a coal export terminal. We prove NP-completeness of the problem and formulate it as a mixed-integer program. We show that for a given reclaiming sequence, the problem can be solved in pseudo-polynomial time. In addition, we provide simple, constant-factor approximation algorithms as well as exact branch-and-bound algorithms. An extensive computational study analyzes the performance of the algorithms.
PubDate: 2016-09-23
DOI: 10.1007/s10951-016-0495-8

• Optimizing railway crew schedules with fairness preferences
• Authors: Silke Jütte; Daniel Müller; Ulrich W. Thonemann
Abstract: Abstract Railway crew scheduling deals with generating duties for train drivers to cover all train movements of a given timetable while taking into account a set of work regulations. The objective is to minimize the overall costs associated with a crew schedule, which includes workforce costs and hotel costs. A cost minimal schedule often contains duties that are unpopular to train drivers, and these unpopular duties are often unevenly distributed among crew depots. At the company that motivated our research, for example, train drivers dislike duties that start in the early morning hours. Currently, some crew depots operate large numbers of these unpopular duties, while others do not have any unpopular duties at all. The train drivers perceive this situation as unfair. They prefer schedules with fewer and more evenly distributed unpopular duties across crew depots. In this paper, we define and measure unpopularity and (un)fairness in a railway crew scheduling context. We integrate fairness conditions into a column generation-based solution algorithm and analyze the effect of increased fairness on cost. We also show how increased fairness affects the unpopularity of a schedule. Our method has been applied to test instances at a large European railway freight carrier. Compared to a standard approach that penalizes only the number of unpopular duties in a schedule, we were able to significantly improve schedule fairness with only marginal increases in schedule cost.
PubDate: 2016-09-23
DOI: 10.1007/s10951-016-0499-4

• Single machine scheduling with a generalized job-dependent cumulative
effect
• Authors: Kabir Rustogi; Vitaly A. Strusevich
Abstract: 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: 2016-09-23
DOI: 10.1007/s10951-016-0497-6

• Increasing airport capacity utilisation through optimum slot scheduling:
review of current developments and identification of future needs
• Authors: Konstantinos G. Zografos; Michael A. Madas; Konstantinos N. Androutsopoulos
Abstract: Abstract Most of the busiest airports worldwide experience serious congestion and delay problems which call for some immediate capacity and demand management action. Solutions aiming to manage congestion through better slot scheduling have lately received a great deal of consideration due to their potential for delivering quick and substantial capacity utilisation improvements. A slot scheduling approach brings promises to cope better with congestion problems in the short to medium run and in a more sustainable way based on existing resources. This paper aims to provide a critical review of current research in declared capacity modelling and strategic slot scheduling. Furthermore, it goes beyond the critical review of current research developments by identifying future research issues and gaps and developing concrete directions towards modelling and solving advanced single airport and network-based slot scheduling problems. Our research findings suggest that the next generation of slot scheduling models should explore variations of currently used objectives (e.g., alternative expressions of schedule delay) and most importantly enrich them with fairness and equity, resource utilisation and environmental considerations. Future modelling efforts should also aim to further investigate airlines’ utility of alternative slot allocation outcomes, including various acceptability measures and levels of tolerance against schedule displacements. Last but not least, future research should intensively focus on the development and validation of computationally viable and robust slot scheduling models being able to capture the complexity, dynamic nature and weather-induced uncertainty of airport operations, along with hybrid solution approaches being able to deal with the size and complexity of slot allocation at network level.
PubDate: 2016-09-22
DOI: 10.1007/s10951-016-0496-7

• Scheduling operating rooms: achievements, challenges and pitfalls
• Authors: Michael Samudra; Carla Van Riet; Erik Demeulemeester; Brecht Cardoen; Nancy Vansteenkiste; Frank E. Rademakers
Abstract: Abstract In hospitals, the operating room (OR) is a particularly expensive facility and thus efficient scheduling is imperative. This can be greatly supported by using advanced methods that are discussed in the academic literature. In order to help researchers and practitioners to select new relevant articles, we classify the recent OR planning and scheduling literature into tables regarding patient type, used performance measures, decisions made, OR up- and downstream facilities, uncertainty, research methodology and testing phase. Based on these classifications, we identify trends and promising topics. Additionally, we recognize three common pitfalls that hamper the adoption of research results by stakeholders: the lack of a clear choice of authors on whether to target researchers (contributing advanced methods) or practitioners (providing managerial insights), the use of ill-fitted performance measures in models and the failure to understandably report on the hospital setting and method-related assumptions. We provide specific guidelines that help to avoid these pitfalls. First, we show how to build up an article based on the choice of the target group (i.e., researchers or practitioners). Making a clear distinction between target groups impacts the problem setting, the research task, the reported findings, and the conclusions. Second, we discuss points that need to be considered by researchers when deciding on the used performance measures. Third, we list the assumptions that need to be included in articles in order to enable readers to decide whether the presented research is relevant to them.
PubDate: 2016-09-06
DOI: 10.1007/s10951-016-0489-6

• Optimization-based resource allocation for software as a service
application in cloud computing
• Authors: Chunlin Li; Yun Chang Liu; Xin Yan
Abstract: Abstract Software as a service (SaaS) is a software that is developed and hosted by the SaaS vendor. SaaS cloud provides software as services to the users through the internet. To provide good quality of service for the user, the SaaS relies on the resources leased from infrastructure as a service cloud providers. As the SaaS services rapidly expand their application scopes, it is important to optimize resource allocation in SaaS cloud. The paper presents optimization-based resource allocation approach for software as a service application in cloud. The paper uses optimization decomposition approach to solve cloud resource allocation for satisfying the cloud user’s needs and the profits of the cloud providers. The paper also proposes a SaaS cloud resource allocation algorithm. The experiments are designed to compare the performance of the proposed algorithm with other two related algorithms.
PubDate: 2016-08-19
DOI: 10.1007/s10951-016-0491-z

• Two-machine flowshop scheduling with three-operation jobs subject to a
fixed job sequence
• Authors: Bertrand M. T. Lin; F. J. Hwang; Jatinder N. D. Gupta
Abstract: Abstract This paper studies the problem of scheduling three-operation jobs in a two-machine flowshop subject to a predetermined job processing sequence. Each job has two preassigned operations, which are to be performed on their respective dedicated machines, and a flexible operation, which may be processed on either of the two machines subject to the processing order as specified. Five standard objective functions, including the makespan, the maximum lateness, the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs are considered. We show that the studied problem for either of the five considered objective functions is ordinary NP-hard, even if the processing times of the preassigned operations are zero for all jobs. A pseudo-polynomial time dynamic programming framework, coupled with brief numerical experiments, is then developed for all the addressed performance metrics with different run times.
PubDate: 2016-08-11
DOI: 10.1007/s10951-016-0493-x

• Open Shop Scheduling with Synchronization
• Authors: C. Weiß; S. Waldherr; S. Knust; N. V. Shakhlevich
Abstract: 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: 2016-08-08
DOI: 10.1007/s10951-016-0490-0

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