Modifying the Assignment Algorithm for the Scheduling of Multiple Competitive Events

 

By Jason L. Jennette

 

Problem Statement

There has been a great deal of study in industrial engineering and operations research on scheduling events and optimizing travel plans. Each of these fields has made great advances in optimizing specialized solutions to a variety of problems. One area that has yet to be addressed is sequence of assignments and reassignments for multiple events over a period of time where the total distances are to be minimized, and numerous constraints are involved.

One of the closest algorithms to approach this is the Assignment algorithm:

 

The assignment problem arises in a variety of decision-making situations. For example, typical assignment problems involve the assigning of jobs to machines, assigning workers to tasks or projects, assigning sales personnel to sales territories, assigning contracts to bidders, and so on. A distinguishing feature of the assignment problem is that one job, worker, etc., is assigned to one and only one machine, project, etc. Specifically, [it looks] for the set of assignments that will optimize a stated objective, such as minimize cost, minimize time, or maximize profits. [2]

 

It can be proven that the assignment algorithm can quickly and easily solve the first collection of assignments. Reapplying the algorithm, however, may produce unsatisfactory results. As more assignments are made, the decisions made early may adversely affect future assignments.

Rather than simply applying the same assignment algorithm for each set of assignments, the algorithm must be modified to take into account previous assignments, and possible future assignments so that better choices can be made for the immediate assignment.

 

Statement of Application

††††††††††† While there could be many applications for such a fast, efficient solution, one of the most common would be in the scheduling of sporting events in a league setting. Each game is the result of a simple assignment of one team, in the role of the visiting team, to another team, in the role of the home team. Since one team can only fill one of the roles in one game on that day, there arises a need to determine which team would best fill that role.

††††††††††† After the first set of games has been selected, the teams will need to again be chosen for the next round of games. The teams that take the role of home teams or road teams may change base on the availability of facilities.

††††††††††† These extra restrictions are certain to make the resulting schedule very complex. In addition, there is always a concern about the distance that must be traveled by a team. Travel between games is a concern as well as travel for the entire season. There needs to be a maximum distance a team is required to travel over a specified time, and each teamís total travel for the season should be relatively equal.

 

Review of the Literature

[1] Anderson, David R., Sweeney, Dennis J., Williams, Thomas A., Joseph, Daniel A. The Management Scientist Version 3.0.West Publishing Co. 1994.

This book includes a small software package and manual that solves the assignment and transportation algorithms. This will be used to check portions of the results from the developed program, and may be used to test extensions of my algorithm is possible.

 

[2] Anderson, David R., Sweeney, Dennis J., Williams, Thomas A., Joseph, Daniel A. Quantitative Methods for Business 5th ed.West Publishing Co. 1994.

This book contains countless examples of Linear Programming problems and their solutions. There is also a large section on the assignment problem, and the Hungarian Method for solving this problem.

 

[3] Atkinson, Kendall. Elementary Numerical Analysis 2nd Ed. John Wiley and Sons, 1993.

This book contains several FORTRAN solutions for various systems of linear equations.

 

[4] Baker, Kenneth R. Introduction to Sequencing and Scheduling John Wiley and Sons, 1974.

This book is a standard in the introduction to sequencing and scheduling problems and their solutions. It provides a short introduction to the concepts of scheduling and then builds up to the more complex problems and their solutions.

 

[5] Dale, Nell, Weems, Chip, and Headington, Mark. Programming and Problem Solving with C++ 2nd Ed. Jones and Bartlett, 2000.

This is astandard C++ textbook. It provides a quick and simple reference to the C++ language, which will be used to test and implement the research results.

 

[6] Foster, Marc: A Proposal for the Realignment of AA Hockey Leagues. At URL http://www.hockeyresearch.com/mfoster/realignment/proposal.html June, 1999

This paper is a standard of reference for hockey related financial and travel data. While this paper mainly focuses on the financial side of scheduling and league alignment, the data related to team travel is invaluable.

 

[7] Hochbaum, Dorit S., ed. Approximation Algorithms for NP-Hard Problems. PWS Publishing, 1997.

This book contains a detailed chapter on the current methods of solving primal-dual algorithms. The book also contains formal proofs of several methods demonstrating that they are solvable in polynomial time.

 

[8] Lawrence, Kenneth D. and Zanakis, Stelios H. Production Planning and Scheduling: Mathematical Programming Applications. Industrial Engineering and Management Press, 1984

This book takes up where Bakerís Introduction book leaves off. This book is a collection of articles by the same authors from various sources. Each article introduces a new problem in the field and describes the solution to the problem using a very algorithmic notation.

 

[9] McCracken, Daniel D., Salmon, William I. Computing for Engineers and Scientists with Fortran 77, 2nd Ed. John Wiley and Sons, 1988.

Much of the code located on the Internet is very old code and in the Fortran 77 language. This book will serve as an aid in converting the code to C++.

 

[10] Syslo, Maciej M., Deo, Narsingh, Kowalik, Janusz S. Discrete Optimization Algorithms with Pascal Programs. Prentice-Hall, 1983.

This book contains several Pascal language implementations of many optimization algorithms. The Ford and Fulkerson method of solving a primal-dual algorithm, which can be used to solve the general transportation problem, is included.

 

Research Objectives

 

Methodology

The completion of the Thesis will require the following tasks:

 

Proposed Schedule of Investigation

††††††††††† (See the chart on the following page.)