Using mixed integer programming to schedule experiments on the Texas A&M University nuclear science center reactor

Abstract

The NSC scheduling problem involves a two-station graphics. bowshot. Several practical aspects prevent it from conforming to existing models in the literature. Some jobs may be preempted, while others may not. Some jobs have deadlines, while others have only due-dates. Some jobs require tooling, while others do not. This problem is modeled as a time-indexed Mixed Integer Program. Constraints were formed and variables were defined in such a way to minimize-to the fullest extent possible-the number of integer variables in the problem. The objective is to minimize the total weighted tardiness of the jobs with due-dates. Deadlines must be observed as constraints. We developed four optimizing strategies and one heuristic and tested them to determine their effectiveness in solving the NSC scheduling problem. One optimizing strategy exploits the Multiple Choice Sets structure within the constraints. The other three optimizing strategies deal with various ways of prioritizing the variables to bias the branch-and-bound search. The higher the priority, the earlier the search branches on that variable. The heuristic starts with the solution to the LP relaxation and fixes all binary variables to 1 that are greater than or equal to some variable k, which is between 0 and 1. These optimizing strategies and the heuristic were tested on 25 test problems, each of which represented a ten-job scheduling problem. The parameters for the jobs were taken from a database of 103 jobs that were processed by the Nuclear Science Center in early 1997. A11 optimizing strategies and the heuristic were tested using CPLEX 6.0. The results of these tests were compared with the CPLEX default settings for solving MIPs. One particular optimizing strategy worked especially well in terms of the number of test problems solved to optimality and the run-time. This "skip-factor'' strategy prioritized variables in such a way that some tardiness is allowed initially in order to arrive at an initial feasible solution quickly. This strategy optimized 80% of the test problems within a predetermined time limit (the highest of all strategies tested) and did so with an average run-time of less than one minute.