  


The Checkpoint Ordering Problem
Philipp Hungerlaender (philipp.hungerlaenderaau.at) Abstract: We suggest a new variant of a row layout problem: Find an ordering of n departments with given lengths such that the total weighted sum of their distances to a given checkpoint is minimized. The Checkpoint Ordering Problem (COP) is both of theoretical and practical interest. It has several applications and is conceptually related to some wellstudied combinatorial optimization problems, namely the SingleRow Facility Layout Problem, the Linear Ordering Problem and a variant of parallel machine scheduling. In this paper we study the complexity of the COP and its special cases. The general version of the COP is NPhard in the weak sense. We propose both a dynamic programming algorithm and an integer linear programming approach for the COP. Our computational experiments indicate that the COP is hard to solve in practice. While the run time of the dynamic programming algorithm strongly depends on the length of the departments, the integer linear programming approach is able to solve instances with up to 25 departments to optimality. Keywords: Combinatorial optimization; dynamic programming; integer linear programming; global optimization; facilities planning and design. Category 1: Linear, Cone and Semidefinite Programming Category 2: Applications  Science and Engineering (Facility Planning and Design ) Category 3: Applications  Science and Engineering (VLSI layout ) Citation: Optimization, accepted, 2017. Download: [PDF] Entry Submitted: 09/15/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  