A linear programming relaxation for scheduling problems

All airlines must perform a large number of maintenances that are prescribed by the Federal Aviation Administration (FAA). The FAA requires each maintenance to be done every N days, and N differs for each maintenance. Although airlines must maintain the planes before N days have passed, maintaining them earlier makes the next deadline sooner.;To research the effectiveness of the algorithms, two generic scheduling problems were studied. The Multiprocessor Scheduling Problem (MSP) has n jobs with lengths of ;These problems were formulated as integer linear programs. Each variable corresponds to a job starting in a certain day. The integer program is too large to solve, but relaxing the integer constraints gives a linear program.;The MSP is feasible when the integer program is feasible. If the linear program is feasible, the integer program is usually feasible. For some special cases of the MSP, the integer program is feasible whenever the linear program is feasible. Simulations were run to calculate bounds on the probability of a MSP having a feasible linear program and an infeasible integer program.;The minimum cost of the integer program for the GTSP is usually strictly larger than the linear program cost. By using the linear program and corresponding fractional solution, heuristics were used to calculate feasible schedules. Bounds were calculated on the percentage cost difference between the heuristics and the actual minimum cost. Some necessary conditions and some sufficient conditions are given for feasibility and optimality.;This thesis describes several heuristic algorithms for the MSP and GTSP. Theoretical results in which the algorithms always work are described along with computational results of the general effectiveness of the algorithms.