Optimization Models for Scheduling of Jobs.

This work is motivated by a particular scheduling problem that is faced by logistics centers that perform aircraft maintenance and modification. Here we concentrate on a single facility (hangar) which is equipped with several work stations (bays). Specifically, a number of jobs have already been scheduled for processing at the facility; the starting times, durations, and work station assignments for these jobs are assumed to be known. We are interested in how best to schedule a number of new jobs that the facility will be processing in the near future. We first develop a mixed integer quadratic programming model (MIQP) for this problem. Since the exact solution of this MIQP formulation is time consuming, we develop a heuristic procedure, based on existing bin packing techniques. This heuristic is further enhanced by application of certain local optimality conditions.

Properties of Labeling Methods for Determining Shortest Path Trees.

A number of labeling procedures for determining shortest paths in a network employ a sequence list in order to carry out the required steps systematically. This paper studies certain formal properties of such sequence lists. It is shown that the desirable property of branching out from nodes whose labels represent actual in-tree distances is assured for certain ways of managing the sequence list, but not for others. The relationship of this property to the computational complexity of various labeling procedures is also investigated.