Solving a Tropical Optimization Problem with Application to Optimal Scheduling

Abstract

A multidimensional optimization problem is formulated and solved in terms of tropical mathematics that is concerned with the theory and applications of semi-rings with idempotent addition. The problem, whose objective function is defined by a matrix, is proposed to be solved via idempotent algebra and tropical optimization tools. A strict lower bound is first derived for the objective function, used for solving the problem, to allow the evaluation of its minimum value. The objective function and its minimum value are then combined into an equation whose complete solution is obtained in the form of all eigenvectors of the matrix. A practical application of the problem is considered using the example of an explicit solution for the optimal scheduling of a project that consists of a set of activities defined by constraints on their start and end times. The optimality criterion for scheduling is defined to minimize the maximum, over all activities, of the working cycle time, which is described as the time interval between the start and the end of the activity. The analytical result extends and supplements the existing algorithmic numerical solutions to optimal scheduling problems. As an illustrative example, the solution of a problem to schedule a project consisting of three activities is presented to illustrate the result.