CLASS SCHEDULING ALGORITHMS FOR NAVY TRAINING SCHOOLS

The problem of developing good schedules for Navy C-Schools has been m odeled as a combinatorial optimization problem. The only complicating feature of the problem is that classes must be grouped together into s equences known as pipelines. An ideal schedule will have all classes i n a pipeline scheduled in consecutive weeks. The objective is to elimi nate the nonproductive time spent by sailors at C-Schools who are wait ing for the next class in a pipeline. In this investigation an implici t enumeration procedure for this problem was developed. The key compon ent of our algorithm is a specialized greedy algorithm which is used t o obtain a good initial incumbent. Often this initial incumbent is eit her an optimal schedule or a near optimal schedule. In an empirical an alysis with the only other competing software system, our greedy heuri stic found equivalent or better solutions in substantially less comput er time. This greedy heuristic was extended and modified for the A-Sch ool scheduling problem and aias found to be superior to its only compe titor. (C) 1998 John Wiley & Sons, Inc.