consortiums

PROJECT 1

SAILOR MARINE CAREER MANAGEMENT SYSTEM

Applications of Random Methods in Combinatorics to Optimization and Scheduling Problems

Tristan Denley, James Reid, Haidong Wu
Department of Mathematics,
University of Mississippi

Proposed Grant $158,500

Abstract:
Bipartite graphs are the fundamental model for time-tabling, allocations, assignment and distribution problems. These graphs

capture the very essence of the interplay between two competing sets of requirements. The document Sailor 21 describes one such scenario Navy Personnel Distribution and Assignment. Sailor 21 discusses the problem of distributing the personnel in such a way that the tasks at hand are manned efficiently and effectively. This problem can be modeled by posing it as a LIST COLORING PROBLEM on a bipartite graph as follows. One of the sides of the bipartite graph is a series of vertices to represent the different sailors (faces) available in the near future. The other side is a series of vertices that represent the different jobs to be done. Edges now run between each job and those faces which are suitable for that task. By placing on each edge a list of time periods during which that face may carry out that job the allocation process is now exactly the task of finding a list coloring of this bipartite graph. A time period is assigned to each edge (a sailor for a given job at a given time) so that a one-to-one correspondence between faces and jobs is obtained.

Retention of Naval Personnel is a crucial consideration in the Naval Personnel Assignment problem. This consideration can be further modeled by the LIST COLORING PROBLEM by assigning weights to the edges to model the desirability of the face-job pairings to the sailor. The LIST COLORING and other assignment problems are discussed in the book published by Cambridge University Press entitled "Bipartite Graphs and their Applications [1]". This book is co-authored by one of the authors of the proposal. The research that the Combinatorics group will accomplish working on this problem and two other associated problems will be discussed in broad detail in the second section of this proposal entitled "Problems and Innovative Methods".