Cost-effective allocations of bounded and binary resources in polynomial time

The problem considered is that of the allocation of linear and discrete resources to concave activities with binary effectiveness values of 0 or 1. The objective is to maximize the ratio of the total return to an affine cost. Previously described algorithms are extended to include an upper bound on the quantity of any resource allocated to given disjoint sets of activities, and on the quantity allocated to any activity from given disjoint sets of resources. It is demonstrated that the algorithm solves the problem in polynomial time.     

Discrete allocation of a linear resource according to a sum-of-products objective

The allocation of a linear resource according to the sum of the returns from independent activities is considered. The return from each activity is given by a product of concave and nondecreasing functions of a single allocation variable. The model can be used, for instance, to describe probabilities of success of several serial tasks, into which an activity is subdivided. An incremental algorithm is defined and conditions are given for the algorithm to generate an optimal solution; otherwise, the problem is solved by a two-step procedure involving the incremental maximization of the return corresponding to a single activity and the combination of the activities by dynamic programming. Examples are given of problems solvable and not solvable by the incremental algorithm.     

Max-min resource allocation

A problem is considered of the allocation of resources so as to maximize the minimum return from several activities. Optimality conditions are given for the case of a single resource, and are used to derive a solution algorithm. Problems with several resources cannot be solved by resourcewise optimization. Concave return functions are treated approximately by linear programming, and optimality or almost optimality of any feasible solution to such a problem can be evaluated by the solution of a linear programming problem. The evaluation measure is extended to certain feasible solutions of problems which have continuous, but not necessarily concave, return functions. A numerical example is given.     

Resource Allocation with Noise Constraints

In the allocation of resources to activities, each activity is described by a concave return function and the sum of the returns is maximized. There are linear constraints on the available quantity of each essential resource. Existing methods for the incremental generation of almost-optimal allocations and for the evaluation of such allocations are extended to include allocations involving "noise" constraints in addition to the linear constraints on the available quantity of each resource. A noise constraint, which is defined in the paper, may be expressed by any relationship, not necessarily linear. An example is given in which the noise constraints take the form of constraints on additional resources.     

Discrete Resource Allocation by a Branch and Bound Method

A branch and bound method given by Shih for the solution of a class of discrete single resource allocation problems with concave return functions and several constraints of any type is extended to cover problems with arbitrary non-decreasing return functions.     

Resource Allocation with Wobbly Functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximisation version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with functions that are not necessarily concave is difficult.In this article, we focus on a large class of problem instances, with objective functions that are close to a concave function or some other smooth function, but with small irregularities in their shape. It is described that these properties are important in many practical situations.The irregularities make it hard or impossible to use known, efficient resource allocation techniques. We show that, for this class of functions the optimal solution can be computed efficiently. We support our claims by experimental evidence. Our experiments show that our algorithm in hard and practically relevant cases runs up to 40–60 times faster than the standard method.     

Fractional Resource Allocation with S-Shaped Return Functions

A fractional resource allocation problem with S-shaped return functions and an affine cost function is considered. Properties of optimal solutions are derived, including conditions for certain allocations to be zero. Conditions are given for the determination of an optimal solution by concave approximations of the return functions; otherwise an error bound is obtained.     

Fuzzy resource allocation

The problem of allocation of fuzzy resources to fuzzy activities is considered. Following a definition of the problem, a dedicated solution algorithm is defined in terms of a linear programming problem in the allocation variables and an aspiration level variable. Applications are given to max-min and sum of returns resource allocation, extending algorithms previously given.     

Allocation of dependent divisional resources

A resource allocation problem is considered with resources that are dependent in the sense that an allocation to an activity requires the application of several resources, except for certain activities which are divisional in the sense that an allocation to such an activity requires the use of only a single resource. Return and cost functions are assumed to be continuous and increasing, and the allocation variables are continuous. Conditions are given for the replacement of the continuous problem by an associated problem with discrete variables and a single constraint, and to a given degree of accuracy. The associated problem can be efficiently solved by dynamic programming. Certain divisional resource allocation problems with discrete variables and several linear constraints are shown to be equivalent to a discrete problem with a single constraint. A numerical example is given.     

Job-shop scheduling with resource-time models of operations

The job-shop problems with allocation of continuously-divisible nonrenewable resource is considered. The mathematical models of operations are linear, decreasing functions with respect to an amount of resource. The objective is sequencing operations and allocation of constrained resource such that the project duration is minimized. Thus, the problem considered is a generalization of the classical job-shop problem. Some properties of the optimal solution are presented. The algorithm of solving this problem is based on the disjunctive graphs theory and branch-and-bound technique. The theory of the algorithm is based on the critical path concept using the segment system approach. The special feature of the algorithm is that it gives a complete solution which is associated with each node of the enumeration tree. Possible generalizations of the results presented are indicated.     

Efficient Resource Allocation with Non-Concave Objective Functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximization version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with non-concave functions is difficult. In this article we show that for fairly well-shaped non-concave objective functions, the optimal solution can be computed efficiently. Our main enabling ingredient is an algorithm for aggregating two objective functions, where the cost depends on the complexity of the two involved functions. As a measure of complexity of a function, we use the number of subintervals that are convex or concave.     

A weak linearization of the Kuhn-tucker conditions for a class of allocation problems

The return obtained from the allocation of resources to an activity is occasionally modelled by means of concave, strictly increasing functions. Exponential functions of a certain class conveniently lend themselves to such modelling. A nonlinear programming formulation of a multiresource allocation problem with return functions of the class appears to have Kuhn-Tucker conditions which in a sense are intrinsically linear. The paper shows how this fact can be utilised to save processing time in the execution of numerical algorithms for the solution of this mathematical programming problem.     

An algorithm for separable non-linear minimax problems

We consider a minimax resource allocation problem in which each term of the objective function is a strictly decreasing, invertible function of a single decision variable. The objective is to minimize the maximum term subject to non-negativity constraints and a set of linear constraints with only non-negative parameters. We develop an algorithm that finds an optimal solution by repeatedly solving a relaxed minimax problem. In general, each relaxed problem is solved by simple search methods; however, for certain non-linear functions the algorithm employs closed form expressions.     

A note ‘On a single machine-scheduling problem with separated position and resource effects’

This note concerns the paper [Janiak A, Kovalyov MY, Lichtenstein M. On a single machine-scheduling problem with separated position and resource effects. Optimization; 2013. doi:10.1080/02331934.2013.804077], which presents an analysis, a counterexample and a pseudocode related with our proof of optimality for a resource allocation algorithm given in [Rudek A, Rudek R. A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models. Comput. Math. Appl. 2011;62:1870–1878]. We show that the discussed analysis is based only on one part of our proof omitting its integral second part, which is the source of misunderstanding. The considered counterexample is applied for an algorithm, which was not the method presented in our paper, whereas our algorithm provides the correct result for the mentioned counterexample. The provided pseudocode of the resource allocation algorithm, which is presented as the correct method, is a pseudocode of the algorithm described in our paper. Therefore, we show that the results presented in our paper are correct.     

Optimal allocation and backup of computer resources under asymmetric information and incentive incompatibility

This paper presents the optimal allocation and backup of computing resources in a multidivisional firm in the presence of asymmetric information and incentive incompatibility. A game-theoretic model is developed and transformed to a linear programming problem. The solution to this linear programming problem enables the corporate headquarters to design a resource allocation scheme such that the revelation principle prevails and all divisions tell the truth. To cope with the combinatorial explosion of complexity caused by the resource constraint, a greedy-type algorithm and an averaged version of the original linear programming problem are developed to provide the upper and lower bounds. The greedy-type algorithm generates exact solutions for a wide range of instances. The lower bounds coincide with the exact solutions for the cases where the computer resource is either scarce or abundant. The averaged-version resource allocation model with slight modifications solves the optimal computer backup capacity problem. It determines how much back up capacity the firm should purchase when the firm's computer breaks down.     

Decentralized Algorithm for Centralized Variational Inequalities in Network Resource Allocation

Decentralized algorithms would be useful for making network resource allocations in large-scale and complex system networks because such networks tend to lack centralized operators and are subject to continuous infrastructure improvements. In this paper, we consider a variational inequality for network resource allocation and devise a decentralized allocation algorithm for it. The proposed algorithm enables each user in the network to decide its own optimal resource allocation in cooperation with other users without using other users’ private information such as their utility functions. Moreover, we present a convergence analysis on the algorithm and apply it to the network resource allocation problem.     

Optimization of a Multiperiod Resource Allocation Model

In this paper we examine multiperiod resource allocation problems, such as allocating a given marketing budget among T periods. The return functions of each period are assumed to be concave functions of the effective effort variable, which is composed of the expenditures in all previous periods and the present one. Assuming that the effect of an amount spent in period t is decreasing by a fixed rate in successive periods, necessary and sufficient conditions for a non-boundary optimal policy are derived. Under these conditions the optimal policy which maximizes total returns is obtained.     

Reflections on a New Approach to Gittins Indexation

Traditional approaches to stochastic resource allocation problems (including the classical multi-armed bandit problems) have usually made use of dynamic programming (DP) methodology, perhaps buttressed by further ad hoc arguments. While such approaches seem ‘natural’ they have usually proved technically very difficult. Bertsimas and Niño-Mora have recently given a radically new account of many important results in this area which relate to Gittins indices. The key to their approach is in the characterisation of the region of achievable performance. The optimisation problems of interest are then solved as linear programs over this region. Here we exploit elements within the Bertsimas and Niño-Mora framework (in particular, its capacity to give formulae for the total return of a given policy in closed form) to obtain (i) a simple dynamic programming proof of the optimality of Gittins index policies and (ii) a range of index-based suboptimality bounds for general policies for a variety of stochastic models for resource allocation.     

Unrelated parallel machines scheduling with deteriorating jobs and resource dependent processing times

We consider unrelated parallel machines scheduling problems involving resource dependent (controllable) processing times and deteriorating jobs simultaneously, i.e., the actual processing time of a job is a function of its starting time and its resource allocation. Two generally resource consumption functions, the linear and convex resource, were investigated. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. This paper focus on the objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. If the number of unrelated parallel machines is a given constant, we show that the problems remain polynomially solvable under the proposed model.     

Resource level minimization in the discrete–continuous scheduling

A discrete–continuous problem of non-preemptive task scheduling on identical parallel processors is considered. Tasks are described by means of a dynamic model, in which the speed of the task performance depends on the amount of a single continuously divisible renewable resource allotted to this task over time. An upper bound on the completion time of all the tasks is given. The criterion is to minimize the maximum resource consumption at each time instant, i.e., the resource level. This problem has been observed in many industrial applications, where a continuously divisible resource such as gas, fuel, electric, hydraulic or pneumatic power, etc., has to be distributed among the processing units over time, and it affects their productivity. The problem consists of two interrelated subproblems: task sequencing on processors (discrete subproblem) and resource allocation among the tasks (continuous subproblem). An optimal resource allocation algorithm for a given sequence of tasks is presented and computationally tested. Furthermore, approximation algorithms are proposed, and their theoretical and experimental worst-case performances are analyzed. Computer experiments confirmed the efficiency of all the algorithms.