Abstract: A problem of the optimal scheduling is considered for a project that consists of a certain set of works to be performed under given constraints on the time of starting and finishing the works. The deviation of the starting time of the works that needs to be minimized is taken as the optimality criterion for scheduling. Such problems arise in project management when it is required, due to technological, organizational, economic, or other reasons, to ensure, wherever possible, that all works start simultaneously. The scheduling problem under consideration is formulated as a constrained minimax optimization problem and then solved using methods of tropical (idempotent) mathematics, which deals with the theory and applications of semirings with idempotent addition. First, a tropical optimization problem is investigated, which is defined in terms of a general idempotent semifield (an idempotent semiring with invertible multiplication), and a complete analytical solution of the problem is derived. The result obtained is then applied to find a direct solution of the scheduling problem in a compact vector form ready for the further analysis of the solutions and straightforward computations. As an illustration, a numerical example of solving a problem of optimal scheduling is given for a project that consists of four works.

Original languageEnglish
Pages (from-to)58-68
Number of pages11
JournalVestnik St. Petersburg University: Mathematics
Volume54
Issue number1
DOIs
StatePublished - Jan 2021

    Scopus subject areas

  • Mathematics(all)

    Research areas

  • idempotent semifield, minimax optimization problem, project management, project scheduling, tropical optimization

ID: 75499029