for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 1952 journals)     - ANIMATION AND SIMULATION (29 journals)    - ARTIFICIAL INTELLIGENCE (96 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 (1138 journals)    - COMPUTER SECURITY (43 journals)    - DATA BASE MANAGEMENT (12 journals)    - DATA MINING (31 journals)    - E-BUSINESS (20 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 (33 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1138 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  [2335 journals]
• 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)

• A memetic algorithm to solve an unrelated parallel machine scheduling
problem with auxiliary resources in semiconductor manufacturing
• Authors: Abdoul Bitar; Stéphane Dauzère-Pérès; Claude Yugma; Renaud Roussel
Pages: 367 - 376
Abstract: Abstract In this paper, we propose a metaheuristic for solving an original scheduling problem with auxiliary resources in a photolithography workshop of a semiconductor plant. The photolithography workshop is often a bottleneck, and improving scheduling decisions in this workshop can help to improve indicators of the whole plant. Two optimization criteria are separately considered: the weighted flow time (to minimize) and the number of products that are processed (to maximize). After stating the problem and giving some properties on the solution space, we show how these properties help us to efficiently solve the problem with the proposed memetic algorithm, which has been implemented and tested on large generated instances. Numerical experiments show that good solutions are obtained within a reasonable computational time.
PubDate: 2016-08-01
DOI: 10.1007/s10951-014-0397-6
Issue No: Vol. 19, No. 4 (2016)

• Dynamic patient admission scheduling with operating room constraints,
flexible horizons, and patient delays
• Authors: Sara Ceschia; Andrea Schaerf
Pages: 377 - 389
Abstract: Abstract We revisit and extend the patient admission scheduling problem, in order to make it suitable for practical applications. The main novelty is that we consider constraints on the utilisation of operating rooms for patients requiring a surgery. In addition, we propose a more elaborate model that includes a flexible planning horizon, a complex notion of patient delay, and new components of the objective function. We design a solution approach based on local search, which explores the search space using a composite neighbourhood. In addition, we develop an instance generator that uses real-world data and statistical distributions so as to synthesise realistic and challenging case studies, which are made available on the web along with our solutions and the validator. Finally, we perform an extensive experimental evaluation of our solution method including statistically principled parameter tuning and an analysis of some features of the model and their corresponding impact on the objective function.
PubDate: 2016-08-01
DOI: 10.1007/s10951-014-0407-8
Issue No: Vol. 19, No. 4 (2016)

• Temporal linear relaxation in IBM ILOG CP Optimizer
• Authors: Philippe Laborie; Jérôme Rogerie
Pages: 391 - 400
Abstract: Abstract IBM ILOG CP Optimizer is a constraint solver that implements a model-and-run paradigm. For scheduling problems, CP Optimizer provides a relatively simple but very expressive modeling language based on the notion of interval variables. This paper presents the temporal linear relaxation (TLR) used to guide the automatic search when solving scheduling problems that involve temporal and resource allocation costs. We give the rationale of the TLR, describe its integration in the automatic search of CP Optimizer, and present the relaxation of most of the constraints and expressions of the model. An experimental study on a set of classical scheduling benchmarks shows that using the TLR is essential for problems with irregular temporal costs and generally helps for problems with resource allocation costs.
PubDate: 2016-08-01
DOI: 10.1007/s10951-014-0408-7
Issue No: Vol. 19, No. 4 (2016)

• Lawler’s minmax cost algorithm: optimality conditions and
uncertainty
• Authors: Nadia Brauner; Gerd Finke; Yakov Shafransky; Dzmitry Sledneu
Pages: 401 - 408
Abstract: Abstract The well-known $$O(n^2)$$ minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an $$O(n^2)$$ algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.
PubDate: 2016-08-01
DOI: 10.1007/s10951-014-0413-x
Issue No: Vol. 19, No. 4 (2016)

• A purely proactive scheduling procedure for the resource-constrained
project scheduling problem with stochastic activity durations
• Authors: Patricio Lamas; Erik Demeulemeester
Pages: 409 - 428
Abstract: Abstract The purpose of this research is to develop a new procedure for generating a proactive baseline schedule for the resource-constrained project scheduling problem. The main advantage of this new procedure is that it is completely independent of the reactive policy applied. This contrasts with the traditional methods that assume a predefined reactive policy. First, we define a new robustness measure, then we introduce a branch-and-cut method for solving a sample average approximation of our original problem. In a computational experiment, we show that our procedure outperforms two other published methods, assuming different robustness measures.
PubDate: 2016-08-01
DOI: 10.1007/s10951-015-0423-3
Issue No: Vol. 19, No. 4 (2016)

• Configuration and the advantages of the shifting bottleneck procedure for
optimizing the job shop total weighted tardiness scheduling problem
• Authors: Yi Tan; Torsten Hildebrandt; Bernd Scholz-Reiter
Pages: 429 - 452
Abstract: Abstract This paper answers two fundamental questions concerning the usage of the shifting bottleneck (SB) procedure to optimize the criterion total weighted tardiness for the classical job shop scheduling problem. The first question is how to configure the SB procedure, as it is a divide-and-conquer method and consists of diverse subsolutions for each procedure phase. The second question is what the advantages of the SB procedure are, in comparison with other state-of-the-art approaches. To answer the first question, we evaluate the performance (i.e. the scheduling quality) and the efficiency (i.e. the computational time) of various SB variants using computational experiments and present guidelines for configuring the SB procedure. To respond to the second question, extensive computational experiments were conducted on various benchmark instances (up to 100 jobs $$\times$$ 20 machines). Results show the superior performance/efficiency trade-off of the SB variants with certain configuration to local search methods. This excellent trade-off between performance and efficiency makes the SB procedure particularly promising for solving practical production scheduling problems.
PubDate: 2016-08-01
DOI: 10.1007/s10951-015-0441-1
Issue No: Vol. 19, No. 4 (2016)

• Late acceptance hill-climbing for high school timetabling
• Authors: George H. G. Fonseca; Haroldo G. Santos; Eduardo G. Carrano
Pages: 453 - 465
Abstract: Abstract The application of the Late Acceptance Hill-Climbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other state-of-art methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHC-based algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms.
PubDate: 2016-08-01
DOI: 10.1007/s10951-015-0458-5
Issue No: Vol. 19, No. 4 (2016)

• Scheduling evacuation operations
• Authors: Kaouthar Deghdak; Vincent T’kindt; Jean-Louis Bouquard
Pages: 467 - 478
Abstract: Abstract In this paper, we consider a large-scale evacuation problem after a major disaster. The evacuation is assumed to occur by means of a fleet of buses, thus leading to scheduling the evacuation operations by buses [(bus evacuation problem (BEP)]. We propose time-indexed formulations as well as heuristic algorithms such as greedy algorithms and a matheuristic. This matheuristic uses the former formulation to improve the best solution obtained by the greedy heuristics. In computational experiments, we analyze and evaluate the efficiency of the proposed solution algorithms.
PubDate: 2016-08-01
DOI: 10.1007/s10951-015-0461-x
Issue No: Vol. 19, No. 4 (2016)

• A Step Counting Hill Climbing Algorithm applied to University Examination
Timetabling
• Authors: Yuri Bykov; Sanja Petrovic
Pages: 479 - 492
Abstract: Abstract This paper presents a new single-parameter local search heuristic named step counting hill climbing algorithm (SCHC). It is a very simple method in which the current cost serves as an acceptance bound for a number of consecutive steps. This is the only parameter in the method that should be set up by the user. Furthermore, the counting of steps can be organised in different ways; therefore, the proposed method can generate a large number of variants and also extensions. In this paper, we investigate the behaviour of the three basic variants of SCHC on the university exam timetabling problem. Our experiments demonstrate that the proposed method shares the main properties with the late acceptance hill climbing method, namely its convergence time is proportional to the value of its parameter and a non-linear rescaling of a problem does not affect its search performance. However, our new method has two additional advantages: a more flexible acceptance condition and better overall performance. In this study, we compare the new method with late acceptance hill climbing, simulated annealing and great deluge algorithm. The SCHC has shown the strongest performance on the most of our benchmark problems used.
PubDate: 2016-08-01
DOI: 10.1007/s10951-016-0469-x
Issue No: Vol. 19, No. 4 (2016)

• Worst-case performance analysis of some approximation algorithms for
minimizing makespan and flowtime
• 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

• A reclaimer scheduling problem arising in coal stockyard management
• 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

• Finding optimal tour schedules on transportation paths under extended time
window constraints
• 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

• 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

• A greedy approximation algorithm for minimum-gap scheduling
• Authors: Marek Chrobak; Uriel Feige; Mohammad Taghi Hajiaghayi; Sanjeev Khanna; Fei Li; Seffi Naor
Abstract: Abstract We consider scheduling of unit-length jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. Polynomial-time algorithms for this problem are known, yet they are rather inefficient, with the best algorithm running in time $$O(n^4)$$ and requiring $$O(n^3)$$ memory. We present a greedy algorithm that approximates the optimum solution within a factor of 2 and show that our analysis is tight. Our algorithm runs in time $$O(n^2 \log n)$$ and needs only O(n) memory. In fact, the running time is $$O(n (g^*+1)\log n)$$ , where $$g^*$$ is the minimum number of gaps.
PubDate: 2016-07-27
DOI: 10.1007/s10951-016-0492-y

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