An extension of set partitioning with application to scheduling problems

DOI10.1016/0377-2217(85)90031-1MaRDI QIDQ1060959zbMATH OpenOpenAlexFDO

Authors Ken Darby-Dowman, Gautam Mitra

Publication date 1985

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL http://bura.brunel.ac.uk/handle/2438/2158

zbMATH Keywords

bus crew scheduling systemextended set partitioninggoal programmingset coveringset packingset partitioningshortest route problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10) Programming involving graphs or networks (90C35)

Review text

The well-known problems of set covering, set partitioning and set packing are defined and their interrelationship is considered. A natural generalization called the extended set partitioning model is presented and the three standard models are shown to be special cases of this generalization. In addition, the extended model includes another type of set problem which can be of greater use in certain applications. The model forms the basis of a computer assisted bus crew scheduling system developed by the authors. The system is in regular use by Dublin City Services in the Republic of Ireland. Finally, the equivalence between a special case of the set partitioning problem and the shortest route problem is considered and it is shown that this equivalence also applies to the extended model.

Recommendations

• A Set Partitioning Approach to the Crew Scheduling Problem
• A dual ascent procedure for the set partitioning problem
• scientific article; zbMATH DE number 1302177
• On the integer properties of scheduling set partitioning models
• A set partitioning reformulation of a school bus scheduling problem

Cites work

• A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling Problem
• A note on two problems in connexion with graphs
• An Essay on Prime Implicant Tables
• An extension of set partitioning with application to scheduling problems
• scientific article; zbMATH DE number 3175708 (Why is no real title available?)
• scientific article; zbMATH DE number 3568354 (Why is no real title available?)
• On a routing problem
• Optimal Political Districting by Implicit Enumeration Techniques
• Set Partitioning: A survey
• The Location of Emergency Service Facilities

Cited in

(20)

• An extension of set partitioning with application to scheduling problems
• On the integer properties of scheduling set partitioning models
• Reformulation of the set partitioning problem as a pure network with special order set constraints
• On some difficult linear programs coming from set partitioning
• Graph theoretic relaxations of set covering and set partitioning problems
• An intelligent system for US Coast Guard cutter scheduling
• A set partitioning approach to shunting
• A review of goal programming and its applications
• The column-circular, subsets-selection problem: Complexity and solutions
• A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints
• Integrated rolling stock deadhead routing and timetabling in urban rail transit lines
• On the extension complexity of scheduling polytopes
• A set partitioning approach to shunting
• scientific article; zbMATH DE number 1302177 (Why is no real title available?)
• Progress in Artificial Intelligence
• Modeling and algorithmic development of a staff scheduling problem
• A model for bus crew scheduling problem with multiple duty types
• Network models for vehicle and crew scheduling
• Partially ordered knapsack and applications to scheduling
• A dual ascent procedure for the set partitioning problem

This page was built for publication: An extension of set partitioning with application to scheduling problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1060959)