Parallel machine scheduling with time windows

This dissertation addresses the problem of scheduling a set of jobs with multiple priorities on nonhomogeneous, parallel machines. The application of interest involves the tracking and data relay satellite system (TDRSS) run by the U.S. National Aeronautics and Space Administration. This system acts as a relay platform for Earth-orbiting vehicles that wish to communicate periodically with ground stations. An additional feature of the problem is that each job falls into one of ρ priority classes. The objective is to maximize the number of jobs scheduled, where a job in a higher priority class has infinitely more value than a job in a lower priority class. The problem is introduced and then compared to other more common scheduling and routing problems. A formal proof that shows the problem to be in NP-hard is presented. Next, mixed-integer linear programming formulations are explained. The difficulty experienced in solving even small instances with CPLEX led to the development of a dynamic programming-like heuristic and a greedy randomized adaptive search procedure (GRASP). The GRASP consists of two phases. The first phase produces feasible solutions by ranking each job with a greedy function and then selecting one at random from a restricted candidate list. The process is repeated until no more jobs can be scheduled. The second phase seeks a local optimum by searching over a series of neighborhoods defined by job insertions and exchanges. Each is described in some detail and then compared using data from a typical busy day scenario. Extensive testing was done on a series of problems randomly generated to reflect a wide range of job characteristics. An exact method was also developed. Here, the problem is reformulated as a set packing problem and a branch-and-price method is applied. The GRASP was used to provide the initial starting solution as well as lower bounds during the branching process. Two methods of branching are presented, one based on time windows and the other based on the special order sets associated with one of the constraints. The proposed procedure was found to be very effective, providing the true optimum for instances with up to 100 jobs and 2 machines. An additional contribution of this work is the development of a technique to randomly generate problem sets with real-world attributes.