Non‐linear programs with max‐linear constraints: a heuristic approach

In multiprocessor interactive systems, a number of products are prepared using simultaneously working processors, each contributing to the completion of every product. The completion times of products can be expressed in terms of the starting times of individual processors as max‐linear functions. It is not difficult to find the starting times once the completion times are given. However, if two such systems work in parallel, it may be necessary to synchronize their work, i.e. to find starting times so that the products are completed at the same time. This task leads to the problem of solving two‐sided max‐linear systems, a problem of undecided computational complexity. If the solution set is non‐trivial, then the task of finding solutions optimal with respect to a certain criterion arises. In this paper, we propose and examine a number of heuristics for solving non‐linear programs with two‐sided max‐linear constraints and compare their performance.