Discrete Optimization

A General Scheme for Solving an NP-hard Problem in the Strong Sense of the Scheduling Theory

O. N. Shul'gina

Kazan State University

Abstract: The well-known strong NP-hard machine scheduling problem, i.e., minimization of the maximal tardiness, is investigated. New properties of the optimal schedule are derived and used to develop a new scheme for solving the above problem.

Presented by the member of Editorial Board: A. I. Kibzun

Received: 27.06.2003

 English version: Automation and Remote Control, 2004, 65:3, 456–463

Bibliographic databases:

• 
• 
• 
•