A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling Problem.

Abstract

An algorithm is presented for the two duty period scheduling problem. This integer programming problem has a binary constraint matrix with two sets of consecutive ones in each column. At each subproblem of a branch and bound procedure, subgradient optimization is used to maximize the value of a Lagrangean relaxation, which is a network flow problem. The algorithm is implemented for the two duty period set partitioning problem, with shortest path relaxations. A second algorithm utilizing the unique properties of prime numbers is developed for solving small subproblems. Computational results are reported for several large problems. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1978
Accession Number
ADA055786

Entities

People

  • Wilfred B. Shepardson

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Business Administration
  • Dynamic Programming
  • Equations
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Numbers
  • Operations Research
  • Optimization
  • Rational Numbers
  • Real Numbers
  • Systems Engineering
  • Trees (Data Structures)

Readers

  • Operations Research