Heterogeneous Scheduling and Rotation
Lecture notes in computer sciencePublished 1 January 2002
Thomas Sjöland, Per Kreuger, Martin Aronsson
Citations4
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This article highlights an application in the area of decision support for planning transports in a railway company utilising constraint logic programming and a flexible design which has been successfully tested on real world data.
Abstract
This article highlights an application in the area of decision support for planning transports in a railway company utilising constraint logic programming and a flexible design which has been successfully tested on real world data. We discuss the problem formulation for the co-ordination of distinct sub-problems, the allocation of track resources to transports, the allocation of vehicles to transports, and the allocation of personnel to perform the transportation tasks in a railway company and the development of a heterogeneous constraint model which is usable also for other production planning problems. Using constraints as the key technology, we discuss approaches to find interfacing principles to combine several solvers.
Keywords
Computer ScienceEngineering
Operations ResearchAlgorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
4,181 Citations1987Marius M. Solomon
This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints and finds that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
Modern heuristic techniques for combinatorial problems
2,623 Citations1993Colin R. Reeves
This chapter discusses combinatorial problems local and global optima heuristics, the tabu framework, and Evaluation of heuristic performance: analytical methods empirical testing statistical inference conclusions.
Operational Research Quarterly (1970-1977)Introduction to Sequencing and Scheduling
2,619 Citations1977A. J. Clewett, Kenneth R. Baker
Elsevier eBooksFoundations of Constraint Satisfaction
1,616 Citations1993
Introduction to the C SP CSP solving - an overview chapter fundamental concepts of the CSP chapter problem reduction chapter basic search strategies for solving CSPs search orders in searching in C SPs exploitation of problem specific features stochastic search methods.
The Journal of Logic ProgrammingConstraint logic programming: a survey
1,332 Citations1994Joxan Jaffar, Michael J. Maher
This survey of CLP is to give a systematic description of the major trends in terms of common fundamental concepts and the three main parts cover the theory, implementation issues, and programming for applications.
Constraint satisfaction in logic programming
1,222 Citations1989Pascal Van Hentenryck
The ideas introduced in "Constraint Satisfaction in Logic Programming " have been used successfully to solve more than a dozen practical problems in operations research and circuit design, including disjunctive scheduling, warehouse location, cutting stock car sequencing, and microcode labeling problems.
INFORMS Journal on ComputingA Computational Study of the Job-Shop Scheduling Problem
901 Citations1991David Applegate, William J. Cook
The optimization procedure, combining the heuristic method and the combinatorial branch and bound algorithm, solved the well-known 10×10 problem of J. F. Thomson in under 7 minutes of computation time on a Sun Sparcstation 1.
Management ScienceAn Algorithm for Solving the Job-Shop Problem
813 Citations1989Jacques Carlier, Éric Pinson
A branch and bound method based on one-machine scheduling problems and made more efficient by several propositions which limit the search tree by using immediate selections for the job-shop problem.
Transportation ScienceA Survey of Optimization Models for Train Routing and Scheduling
778 Citations1998Jean‐François Cordeau, Paolo Toth +1 more
A survey of recent optimization models for the most commonly studied rail transportation problems is presented and a classification of models is proposed and their important characteristics are described by focusing on model structure and algorithmic aspects.
Annals of Operations ResearchLocal search in routing problems with time windows
660 Citations1985Martin Savelsbergh
This work develops local search algorithms for routing problems with time windows based on thek-interchange concept and considers the problem of finding initial solutions.
Transportation ScienceSurvey Paper—Time Window Constrained Routing and Scheduling Problems
540 Citations1988Marius M. Solomon, Jacques Desrosiers
Having surveyed the state-of-the-art in this area, the aim of this paper is to survey the significant advances made for the following classes of routing problems with time windows: the single and multiple traveling salesmanproblem, the shortest path problem, the minimum spanning tree problem, and the generic vehicle routing problem.
European Journal of Operational ResearchA parallel route building algorithm for the vehicle routing and scheduling problem with time windows
416 Citations1993Jean‐Yves Potvin, Jean‐Marc Rousseau
This paper describes an insertion algorithm for the Vehicle Routing and Scheduling Problem with Time Windows that builds routes in parallel and uses a generalized regret measure over all unrouted customers to select the next candidate for insertion.
NetworksRouting with time windows by column generation
361 Citations1984Jacques Desrosiers, François Soumis +1 more
This work uses column generation on a set partitioning problem solved by simplex and branch-and-bound to determine the number of vehicles required, together with their routes and schedules, so that each trip begins within its given time interval, while the fixed costs related to thenumber of vehicles, and the travel costs between trips, are minimized.
Mathematical and Computer ModellingIntroducing global constraints in CHIP
310 Citations1994Nicolas Beldiceanu, Évelyne Contejean
This paper shows how the introduction of new primitive constraints over finite domains in the constraint logic programming system CHIP result in finding very rapidly good solutions for a large class of difficult sequencing, scheduling, geometrical placement and vehicle routing problems.
Mathematical and Computer ModellingExtending chip in order to solve complex scheduling and placement problems
299 Citations1993Abderrahmane Aggoun, Nicolas Beldiceanu
It is shown how the introduction of a new primitive constraint over finite domains in the constraint logic programming system CHIP allows us to find very good solutions for a large class of very difficult scheduling and placement problems.
Operations ResearchCyclic Transfer Algorithm for Multivehicle Routing and Scheduling Problems
293 Citations1993Paul M. Thompson, Harilaos N. Psaraftis
This paper investigates the application of a new class of neighborhood search algorithms—cyclic transfers—to multivehicle routing and scheduling problems and shows that cyclic transfer methods are either comparable to or better than the best published heuristic algorithms for several complex and important vehicle routing and schedules problems.
Concurrent constraint programming languages
255 Citations1989Dana Scott, Vijay Saraswat
This thesis develops the framework of concurrent constraint programming, and presents a compiler for a (superset of) Atomic Herbrand, a cc language over the Herbrand constraint system, and a number of constraint systems which may be used to instantiate the cc family of languages.
European Journal of Operational ResearchAdjustment of heads and tails for the job-shop problem
241 Citations1994Jacques Carlier, Éric Pinson
A new lower bound and a new branching scheme which are used to design a branch and bound method are described and Computational results show that these techniques permit to drastically reduce the size of the search trees.
Mathematical ProgrammingDiscrete optimization in public rail transport
220 Citations1997Michael R. Bussieck, Thomas Winter +1 more
Many problems arising in traffic planning can be modelled and solved using discrete optimization, and this chapter focuses on recent developments which were applied to large scale real world instances.
Operations ResearchA Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem
212 Citations1994Celso C. Ribeiro, François Soumis
A new formulation to the multiple-depot vehicle scheduling problem as a set partitioning problem with side constraints is given, whose continuous relaxation is amenable to be solved by column generation, which provides a much tighter lower bound than the additive bound procedure previously applied to this problem.
Annals of Operations ResearchA practical use of Jackson's preemptive schedule for solving the job shop problem
184 Citations1990Jacques Carlier, Éric Pinson
This paper presents a polynomial algorithm for optimally adjusting heads and tails in the job shop problem based on Jackson's preemptive schedule for the one-machine problem and uses this algorithm to construct a new branch and bound method.
Hierarchical A *: searching abstraction hierarchies efficiently
134 Citations1996Robert C. Holte, M. B. Perez +2 more
A new abstraction-induced search technique, "Hierarchical A*", is introduced that gets around two difficulties: first, by drawing from a different class of abstractions, "homomorphism abstractions," and, secondly, by using novel caching techniques to avoid repeatedly expanding the same states in successive searches in the abstract space.
Artificial IntelligenceSpeeding up problem solving by abstraction: a graph oriented approach
110 Citations1996Robert C. Holte, Taieb. Mkadmi +2 more
Experiments comparing these techniques on a variety of problems show that alternating opportunism (AltO) a variant of the new technique, is uniformly superior to all the others.
Naval Research Logistics (NRL)Scheduling tasks with sequence-dependent processing times
104 Citations1988Lucio Bianco, Salvatore Ricciardelli +2 more
OR SpectrumA branch & bound method for the general-shop problem with sequence dependent setup-times
102 Citations1996Peter Brucker, Olaf Thiele
NetworksOn the worst‐case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints
101 Citations1986Marius M. Solomon
Analysis of approximation methods for the vehicle routing and scheduling problem with time window constraints shows that their worst-case behavior on n customer problems is at least order of n for minimizing the number of vehicles used, the total distance traveled, and the total schedule time.
Lecture notes in computer scienceGlobal Constraints as Graph Properties on a Structured Network of Elementary Constraints of the Same Type
94 Citations2000Nicolas Beldiceanu
This paper introduces a classification scheme for global constraints based on a small number of basic ingredients from which one can generate almost all existing global constraints and come up with new interesting constraints.
A theoretical and experimental comparison of constraint propagation techniques for disjunctive scheduling
90 Citations1995Philippe Baptiste, Claude Le Pape
The main result of the study is an implementation of the rst method in Ilog Schedule, a generic tool for constraint-based scheduling which exhibits performance in the same range of e ciency as speci c operations research algorithms.
Management ScienceSome Heuristics for Scheduling Jobs on Parallel Machines with Setups
66 Citations1990Kut C. So
Three heuristics for solving the problem of scheduling jobs on parallel machines with setup times by finding a feasible schedule for each machine which maximizes the total reward are studied.
International Journal of Production ResearchSequence dependent set-up times and job sequencing
65 Citations1977Charles H. White, Richard C. Wilson
A procedure that classifies set-up operations and predicts the set- up times is developed and a method for sequencing the jobs so as to minimize the total set-ups time is developed.
New Generation ComputingProgramming languages for distributed applications
64 Citations1998Seif Haridi, Peter Van Roy +2 more
This work has designed and built a platform that separates an application’s functionality from its distribution structure and efficiently implements Distributed Oz, which extends the Oz language with constructs to express the distributionructure and with basic primitives for open computing, failure detection and handling, and resource control.
Operations ResearchTechnical Note—A Scheduling Problem Involving Sequence Dependent Changeover Times
42 Citations1972Andrew Lockett, A.P. Mühlemann
A branch-and-bound algorithm is derived, which has been shown to be computationally restrictive at the present time, for scheduling jobs on a machine using various machine tools in which considerable changing of the tools is necessary, and the changeover time depends critically on the previous jobs.
Lecture notes in computer scienceSpeeding up constraint propagation by redundant modeling
40 Citations1996B. M. W. Cheng, Jimmy H. M. Lee +1 more
A simple modeling and programming approach for speeding up constraint propagation based on the concept of redundant modeling is described, and how mutually redundant models can be combined and connected using channeling constraints is shown.
American Journal of Mathematical and Management SciencesVehicle Routing with Time-Window Constraints
25 Citations1986Bruce Golden, Arjang A. Assad
INFORMS Journal on ComputingA Comparison of Constraint and Mixed-Integer Programming Solvers for Batch Sequencing with Sequence-Dependent Setups
18 Citations1995Carsten Jordan, Andreas Drexl
A batch sequencing model with sequence-dependent setup-times and -costs is used to compare modeling and solving with two different general solvers and the performance of the constraint versus the mixed-integer programming solver is compared.
Sequence dependent task extensions for trip scheduling
9 Citations2001Per Kreuger, Mats Carlsson +2 more
The report concluded that the removal of the coating produced a decrease in the mechanical properties of the substrates and the hardness and tensile strength in Al-Mg decreases between 20–27% and in aluminized steel between 10–11%.
Publications (Konstfack University of Arts, Crafts, and Design)Knowledge-based Locomotive Planning for the Swedish Railway
6 Citations2000Volker Scholtz
This report describes a vehicle routing and scheduling problem occurring in the planning of rail traffic at the Swedish State Railways (SJ) and describes several techniques that can be used to address the problem.
The MIT Press eBooksConstraint Programming in Oz
5 Citations1997
The themes of the 1997 conference are new theoretical and practical accomplishments in logic programming, new research directions where ideas originating from logic programming can play a fundamental role, and relations between logic programming and other fields of computer science.
Publications (Konstfack University of Arts, Crafts, and Design)Task Structure Abstraction
2 Citations2001Simon Lindblom, Martin Aronsson +1 more
It is claimed that properties of such operations can be used to characterise reasoning in coordination problems, and a model of such a problem from the rail transport industry formalised as several task structures is presented.
Giornale italiano di cardiologia (2006)ACOOR Rapport 1; Tuff: Systemöversikt och arkitektur
2 Citations2000Martin Aronsson, Per Kreuger +2 more
Publications (Konstfack University of Arts, Crafts, and Design)The use of abstractions to solve large scheduling problems
1 Citations2000Per Holmberg
This thesis investigates how abstractions can be used to improve performance in a railroad scheduling system that uses constraint programming and shows that net abstraction works best for problems with many valid solutions.
KTH Publication Database DiVA (KTH Royal Institute of Technology)ACOOR Rapport 2: Översikt av tekniker och metoder
1 Citations2000Simon Lindblom, Per Kreuger +2 more