Optimization Online


The Checkpoint Ordering Problem

Philipp Hungerlaender (philipp.hungerlaender***at***aau.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 well-studied combinatorial optimization problems, namely the Single-Row 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 NP-hard 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
Entry Accepted: 09/16/2014
Entry Last Modified: 07/15/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society