A Decomposition Approach for Shipboard Manpower Scheduling

Abstract

This paper presents a model and procedure for determining crew composition for a new technology like the Navy's DDX. Here the prototype DDX manpower scheduling problem is modeled as a project scheduling problem with multi-purpose resources (PSMPR) where multi-skilled sailors form teams to accomplish interrelated onboard tasks. A hybrid decomposition algorithm that incorporates constraint programming (CP) and a tabu search (TS) metaheuristic is developed for solving this NP-hard problem. In computational experiments, the performance of our hybrid algorithm is tested and compared with solutions found using mixed-integer linear programming (MILP) with CPLEX and with lower bounds obtained from a bin packing problem with conflicts (BPC).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2009
Accession Number
ADA543926

Entities

People

  • Haitao Li
  • Keith Womer

Organizations

  • University of Missouri

Tags

Communities of Interest

  • Energy and Power Technologies
  • Ground and Sea Platforms
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Business Administration
  • Computer Programming
  • Engineering
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Military Operations
  • Navy
  • Operations Research
  • Optimization
  • Project Management
  • Scheduling (Production)
  • Ships
  • Systems Engineering
  • United States

Fields of Study

  • Computer science

Readers

  • Naval Architecture and Marine Engineering.
  • Operations Research