for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 1980 journals)     - ANIMATION AND SIMULATION (29 journals)    - ARTIFICIAL INTELLIGENCE (98 journals)    - AUTOMATION AND ROBOTICS (97 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 (1154 journals)    - COMPUTER SECURITY (45 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 (98 journals)    - INTERNET (91 journals)    - SOCIAL WEB (49 journals)    - SOFTWARE (34 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1154 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]
• 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
Pages: 3 - 24
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: 2017-02-01
DOI: 10.1007/s10951-016-0496-7
Issue No: Vol. 20, No. 1 (2017)

• Optimizing railway crew schedules with fairness preferences
• Authors: Silke Jütte; Daniel Müller; Ulrich W. Thonemann
Pages: 43 - 55
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: 2017-02-01
DOI: 10.1007/s10951-016-0499-4
Issue No: Vol. 20, No. 1 (2017)

• An integrated model for the transshipment yard scheduling problem
• Authors: Mateusz Cichenski; Florian Jaehn; Grzegorz Pawlak; Erwin Pesch; Gaurav Singh; Jacek Blazewicz
Pages: 57 - 65
Abstract: Abstract A hub-and-spoke railway system is an efficient way of handling freight transport by land. A modern rail–rail train yard consists of huge gantry cranes that move the containers between the trains. In this context, we consider a rail–rail transshipment yard scheduling problem (TYSP) where the containers arrive to the hub and need to be placed on a train that will deliver them to their destination. In the literature, the problem is decomposed hierarchically into five subproblems, which are solved separately. First, the trains have to be grouped into bundles in which they visit the yard. Next, the trains have to be assigned to tracks within these bundles, namely parking positions. Then the final positions for the containers on trains have to be determined. Next, the container moves that need to be performed are assigned to the cranes. Finally, these moves have to be sequenced for each crane for processing. In this paper, an integrated MILP model is proposed, which aims to solve the TYSP as a single optimization problem. The proposed formulation also enables us to define more robust and complex objective functions that include key characteristics from each of the above-mentioned subproblems. The strength of our proposed formulation is demonstrated via computational experiments using the data from the literature. Indeed, the results show that the TYSP can be solved without the use of decomposition techniques and more insight can be obtained from the same input data used to solve particular single decomposed subproblems.
PubDate: 2017-02-01
DOI: 10.1007/s10951-016-0470-4
Issue No: Vol. 20, No. 1 (2017)

• Real-time management of berth allocation with stochastic arrival and
handling times
• Authors: Nitish Umang; Michel Bierlaire; Alan L. Erera
Pages: 67 - 83
Abstract: Abstract In this research we study the berth allocation problem (BAP) in real time as disruptions occur. In practice, the actual arrival times and handling times of the vessels deviate from their expected or estimated values, which can disrupt the original berthing plan and possibly make it infeasible. We consider a given baseline berthing schedule, and solve the BAP on a rolling planning horizon with the objective to minimize the total realized cost of the updated berthing schedule, as the actual arrival and handling time data is revealed in real time. The uncertainty in the data is modeled by making appropriate assumptions about the probability distributions of the uncertain parameters based on past data. We present an optimization-based recovery algorithm based on set partitioning and a smart greedy algorithm to reassign vessels in the event of disruption. Our research problem derives from the real-world issues faced by the Saqr port, Ras Al Khaimah, UAE, where the berthing plans are regularly disrupted owing to a high degree of uncertainty in information. A simulation study is carried out to assess the solution performance and efficiency of the proposed algorithms, in which the baseline schedule is the solution of the deterministic BAP without accounting for any uncertainty. Results indicate that the proposed reactive approaches can significantly reduce the total realized cost of berthing the vessels as compared to the ongoing practice at the port.
PubDate: 2017-02-01
DOI: 10.1007/s10951-016-0480-2
Issue No: Vol. 20, No. 1 (2017)

• Scheduling reclaimers serving a stock pad at a coal terminal
• Authors: Thomas Kalinowski; Reena Kapoor; Martin W. P. Savelsbergh
Pages: 85 - 101
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: 2017-02-01
DOI: 10.1007/s10951-016-0495-8
Issue No: Vol. 20, No. 1 (2017)

• Optimization-based resource allocation for software as a service
application in cloud computing
• Authors: Chunlin Li; Yun Chang Liu; Xin Yan
Pages: 103 - 113
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: 2017-02-01
DOI: 10.1007/s10951-016-0491-z
Issue No: Vol. 20, No. 1 (2017)

• Improved algorithms for resource allocation under varying capacity
• Authors: Venkatesan T. Chakaravarthy; Anamitra R. Choudhury; Shalmoli Gupta; Sambudha Roy; Yogish Sabharwal
Abstract: Abstract We consider the problem of scheduling a set of jobs on a system that offers certain resource, wherein the amount of resource offered varies over time. For each job, the input specifies a set of possible scheduling instances, where each instance is given by starting time, ending time, profit and resource requirement. A feasible solution selects a subset of job instances such that at any timeslot, the total requirement by the chosen instances does not exceed the resource available at that timeslot, and at most one instance is chosen for each job. The above problem falls under the well-studied framework of unsplittable flow problem on line. The generalized notion of scheduling possibilities captures the standard setting concerned with release times and deadlines. We present improved algorithms based on the primal–dual paradigm, where the improvements are in terms of approximation ratio, running time and simplicity.
PubDate: 2017-02-16
DOI: 10.1007/s10951-017-0515-3

• Mathematical models for the berth allocation problem in dry bulk terminals
• Authors: Andreas T. Ernst; Ceyda Oğuz; Gaurav Singh; Gita Taherkhani
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-02-16
DOI: 10.1007/s10951-017-0510-8

• Single machine scheduling with job delivery to multiple customers
• Authors: Jianming Dong; Xueshi Wang; Jueliang Hu; Guohui Lin
Abstract: Abstract We investigate a single machine scheduling problem with job delivery to multiple customers. In this problem, each job needs to be processed on the single machine, and then delivered by a single vehicle to its customer, where the job has a physical size representing the fraction of space it occupies on the vehicle. The vehicle delivers a shipment from the machine to a customer and has to return back to the machine for delivering the next shipment. It takes different constant time for the round trips between the machine and the different customers. The goal is to minimize the makespan, by that time all the jobs are processed and delivered to their respective customers, and the vehicle returns back to the machine. We propose a 2-approximation algorithm for the general case; when there are only two customers, we present an improved 5/3-approximation algorithm. The design and performance analysis of these two algorithms integrate several known results and techniques for the single machine scheduling problem, the bin-packing problem, and the knapsack problem.
PubDate: 2017-02-15
DOI: 10.1007/s10951-017-0508-2

• The equivalence of two classical list scheduling algorithms for dependent
typed tasks with release dates, due dates and precedence delays
• Authors: Aurélien Carlier; Claire Hanen; Alix Munier Kordon
Abstract: Abstract We consider a finite set of unit time execution tasks with release dates, due dates and precedence delays. The machines are partitioned into k classes. Each task requires one machine from a fixed class to be executed. The problem is the existence of a feasible schedule. This general problem is known to be $$\mathcal {NP}$$ -complete; many studies were devoted to the determination of polynomial time algorithms for some special subcases, most of them based on a particular list schedule. The Garey–Johnson and Leung–Palem–Pnueli algorithms (respectively GJ and LPP in short) are both improving the due dates to build a priority list. They are modifying them using necessary conditions until a fixed point is reached. The present paper shows that these two algorithms are different implementations of the same generic one. The main consequence is that all the results valid for GJ algorithm are also for LPP and vice versa.
PubDate: 2017-02-14
DOI: 10.1007/s10951-016-0507-8

• Journal of Scheduling (2017)
• Authors: Edmund Burke; Michael Pinedo
PubDate: 2017-02-02
DOI: 10.1007/s10951-017-0509-1

• Online interval scheduling with a bounded number of failures
• Authors: Marco Bender; Clemens Thielen; Stephan Westphal
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-01-13
DOI: 10.1007/s10951-016-0506-9

• New strategies for stochastic resource-constrained project scheduling
• Authors: Salim Rostami; Stefan Creemers; Roel Leus
Abstract: Abstract We study the stochastic resource-constrained project scheduling problem or SRCPSP, where project activities have stochastic durations. A solution is a scheduling policy, and we propose a new class of policies that is a generalization of most of the classes described in the literature. A policy in this new class makes a number of a priori decisions in a preprocessing phase, while the remaining scheduling decisions are made online. A two-phase local search algorithm is proposed to optimize within the class. Our computational results show that the algorithm has been efficiently tuned toward finding high-quality solutions and that it outperforms all existing algorithms for large instances. The results also indicate that the optimality gap even within the larger class of elementary policies is very small.
PubDate: 2017-01-12
DOI: 10.1007/s10951-016-0505-x

• Online bin stretching with three bins
• Authors: Martin Böhm; Jiří Sgall; Rob van Stee; Pavel Veselý
Abstract: 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-01-11
DOI: 10.1007/s10951-016-0504-y

• Optimizing memory allocation for multistage scheduling including setup
times
• Authors: Anne Benoit; Mathias Coqblin; Jean-Marc Nicod; Veronika Rehn-Sonigo
Pages: 641 - 658
Abstract: Abstract Mapping linear workflow applications onto a set of homogeneous processors can be optimally solved in polynomial time for the throughput objective with fewer processors than stages. This result holds true even when setup times occur in the execution and homogeneous buffers are available for the storage of intermediate results. In this kind of application, several computation stages are interconnected as a linear application graph, and each stage holds a buffer of limited size where intermediate results are stored and a processor setup time occurs when passing from one stage to another. In this paper, we tackle the problem in which the buffer sizes are not given beforehand and must be fixed before the execution to maximize the throughput within each processor. The goal of this work is to minimize the cost induced by the setup times by allocating buffers that are proportinal in size to each other. We present a closed formula to compute the optimal buffer allocation in the case of nondecreasing setup costs in the linear application. For the case of unsorted setup times, we provide competitive heuristics that are validated via extensive simulation. Three nonscalable brute force algorithms are also provided to compare heuristic approaches to optimal ones for small applications and to evaluate the relevance of our approach.
PubDate: 2016-12-01
DOI: 10.1007/s10951-015-0437-x
Issue No: Vol. 19, No. 6 (2016)

• Scheduling on parallel identical machines with late work criterion:
Offline and online cases
• Authors: Xin Chen; Malgorzata Sterna; Xin Han; Jacek Blazewicz
Pages: 729 - 736
Abstract: Abstract In the paper, we consider the problem of scheduling jobs on parallel identical machines with the late work criterion and a common due date, both offline and online cases. Since the late work criterion has not been studied in the online mode so far, the analysis of the online problem is preceded by the analysis of the offline problem, whose complexity status has not been formally stated in the literature yet. Namely, for the offline mode, we prove that the two-machine problem is binary NP-hard, and the general case is unary NP-hard. In the online mode we assume that jobs arrive in the system one by one, i.e., we consider the online over list model. We give an algorithm with a competitive ratio being a function of the number of machines, and we prove the optimality of this approach for two identical machines.
PubDate: 2016-12-01
DOI: 10.1007/s10951-015-0464-7
Issue No: Vol. 19, No. 6 (2016)

• Scheduling with time-dependent discrepancy times
• Authors: Florian Jaehn; Helmut A. Sedding
Pages: 737 - 757
Abstract: Abstract In time-dependent scheduling, various processing time functions are studied, yet absolute value functions have surprisingly been omitted from the discussion. Such a processing time function increases linearly with a job’s discrepancy from its ideal midtime. The objective is to find a schedule that minimizes the makespan, introducing the discrepancy time minimization problem. This single-machine scheduling problem with time-dependent processing times is motivated by optimization of walking times on a car assembly line. Its decision version is NP hard, as we show by reduction of the even–odd partition problem. For the variant with known start time, we develop several heuristics. Further insights form lower bounds and dominance rules for a branch-and-bound search. Numerical experiments show the performance of our algorithms on problem instances of up to 60 jobs. For the variant with common ideal midtime and flexible start time, we present a polynomial-time algorithm.
PubDate: 2016-12-01
DOI: 10.1007/s10951-016-0472-2
Issue No: Vol. 19, No. 6 (2016)

• On scheduling with non-increasing time slot cost to minimize total
weighted completion time
• Authors: Yingchao Zhao; Xiangtong Qi; Minming Li
Pages: 759 - 767
Abstract: Abstract This paper addresses a recent open scheduling problem which aims to minimize the summation of total weighted completion time and the total machine time slot cost. Focusing on the case of non-increasing time slot cost with non-preemptive jobs, we show that the problem can be solved in polynomial-time when the time slot cost decreases with certain patterns, including linearly decreasing, decreasing concave, and decreasing convex cases. Different methodologies are used for three cases. For the linearly decreasing case, we can classify all the jobs into three categories and schedule the job sets one by one. For the decreasing concave case, we calculate each job’s worst starting time and try to make them far away from their worst starting times. For the decreasing concave case, we calculate each job’s best starting time and let them start close to their best starting times. Finally, we show that the problem is NP-hard in the strong sense when the time slot cost decreases in an arbitrary way.
PubDate: 2016-12-01
DOI: 10.1007/s10951-015-0462-9
Issue No: Vol. 19, No. 6 (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 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

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