Notes on Algorithms and Complexity

From a 1993 handbook on OR and MS

Sequencing and Scheduling.

Definition:optimal allocation of scarce resources to activities over time.

Algorithms and Complexity

Complexity Theory : provides a mathematical framework where mathematical problems can be classified as "easy" or "hard"

NP Complete problem :  hardest problem in NP, meaning in that if it is solvable, then each problem in NP would be solvable.
so P=NP
NP-completeness - strong evidence that a polynomial time algorithm does not exist.

A problem is NP-complete if every problem is NP and it reduces to NP-complete

Optimization problem is NP Hard - if the associated decision problem is NP-complete.

optimization problem is NP Hard - meaning it is impossible to always find an optimal solution quickly.
possible to have some approximation algorithms.

Arbitrary precedence constraints, release dates, deadlines

if release dates are specified, makes the problem strongly NP Hard.

when jobs have to meet deadlines : shown to be NP- Hard by Lawler

Many have developed elimination criteria. i.e., of it meets certain criteria for tasks, then schedule, etc.
if elimination criteria are met then the problem can be approximated to polynomial time.

The rest of the chapter examines each type of scheduling problem ones with uniform processors, heterogeneous processor, job-shop.

There is a reference to Ibarra and Kim from which I'd somewhat understood the scheduling problem.