Worst‐case allocation algorithms in a complex of operations with interval parameters

In many decision‐making problems under parameter uncertainty, the most popular stochastic approach is not used because of its serious drawbacks. The purpose of this paper is to present another approach, which copes with the uncertainty of parameters. It uses a precise criterion evaluating a decision with respect to uncertain parameters. This precision by the maximum operator is performed on a term based on the criterion and called the relative regret. The approach is applied to the allocation problems in a complex of operations.

The resource allocation problems in a complex of operations of independent and dependent structures to minimize a total execution time of all operations are investigated. Then, the results are extended for the problem of a task allocation in the complex of independent operations. The case is considered when the parameters in the functional models of the operations are uncertain, and their values belong to the intervals of known bounds. The solution algorithms for the uncertain problems are based on known solution algorithms for the corresponding deterministic problems. The solution algorithms for the latter problems are outlined in the paper.

The main contribution of the paper consists in presenting the property that it is possible for the uncertain problems considered to replace the solution of the uncertain allocation problems by solving a number of corresponding deterministic problems.

The useful and interesting property of the solution algorithm for the allocation problems, in general, cannot be applied to the other decision‐making problems under uncertainty. As an example of such a problem, a simple routing‐scheduling problem is presented for which, however, a number of possible parameter scenarios can be substantially limited.

The allocation problems addressed in the paper have a variety of applications in computer systems and in manufacturing systems. Moreover, a lack of crisp values for the parameters in models of individual operations is rather common.

The paper extends previous results for the allocation problems in a complex of operations.