Tropical optimization technique in bi-objective project scheduling under temporal constraints
- PDF / 473,027 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 179 Views
Tropical optimization technique in bi-objective project scheduling under temporal constraints Nikolai Krivulin1 Received: 12 April 2020 / Accepted: 4 June 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We consider a project that consists of a set of activities performed in parallel under constraints on their start and finish times, including start-finish precedence relationships, release start times, release end times, and deadlines. The problems of interest are to decide on the optimal schedule of the activities to minimize both the maximum flow-time over all activities, and the project makespan. We formulate these problems as bi-objective optimization problems in the framework of tropical mathematics which investigates the theory and applications of algebraic systems with idempotent operations and has various applications in management science and operations research. Then, the use of methods and techniques of tropical optimization allows to derive complete Pareto-optimal solutions of the problems in a direct explicit form ready for further analysis and straightforward computation. We discuss the computational complexity of the solution and give illustrative examples. Keywords Decision analysis · Multiple criteria evaluation · Max-plus algebra · Tropical optimization · Time-constrained project scheduling Mathematics Subject Classification 90C24 · 15A80 · 90C29 · 90B50 · 90B35
1 Introduction Tropical optimization deals with optimization problems that are formulated and solved in terms of tropical (idempotent) mathematics which concentrates on the theory and applications of algebraic systems with idempotent operations. Methods and techniques of tropical mathematics find application in operations research, management science
This work was supported in part by the Russian Foundation for Basic Research (Grant Number 20-010-00145).
B 1
Nikolai Krivulin [email protected] St. Petersburg State University, Universitetskaya nab. 7/9, St. Petersburg, Russia 199034
123
N. Krivulin
and other fields, where tropical optimization allows to provide new efficient solutions to both known and novel optimization problems of practical importance. Since the pioneering works by Pandit (1961), Cuninghame-Green (1962), Giffler (1963), Hoffman (1963) and Vorobjev (1963) on tropical mathematics in the early 1960s, optimization problems have served to motivate and illustrate the study. Further research in succeeding decades were often concerned with the analysis and solution of optimization problems as well. The results obtained in the area are presented in a number of contributed papers and books, among which are monographs by Baccelli et al. (1993), Kolokoltsov and Maslov (1997), Golan (2003), Fiedler et al. (2006), Heidergott et al. (2006), Gondran and Minoux (2008) and Gavalec et al. (2015). Many tropical optimization problems consist in minimizing or maximizing functions defined in the tropical mathematics setting on vectors over idempotent semifields (semirings with idempotent addition and invertible
Data Loading...
