Skill-based framework for optimal software project selection and resource allocation

This paper presents a conceptual framework and a mathematical formulation for software resource allocation and project selection at the level of software skills. First, we introduce a skill-based framework that considers universities, software companies, and potential projects of a country. Based on this framework, we formulate a linear integer program PMax which determines the selection of projects and the allocation of human resources that maximize profit for a certain company. We show that PMax is NP-complete. Therefore, we devise a meta-heuristic, called Tabu Select and Greedily Allocate (TSGA), to overcome the computational complexities. When compared to PMax running on CPLEX, TSGA performs 15 times faster with an accuracy of 98% on small to large size problems where CPLEX converges. On larger problems where CPLEX does not return an answer, TSGA computes a feasible solution in the order of minutes.     

Optimal resource allocation for security in reliability systems

Recent results have used game theory to explore the nature of optimal investments in the security of simple series and parallel systems. However, it is clearly important in practice to extend these simple security models to more complicated system structures with both parallel and series subsystems (and, eventually, to more general networked systems). The purpose of this paper is to begin to address this challenge. While achieving fully general results is likely to be difficult, and may require heuristic approaches, we are able to find closed-form results for systems with moderately general structures, under the assumption that the cost of an attack against any given component increases linearly in the amount of defensive investment in that component. These results have interesting and sometimes counterintuitive implications for the nature of optimal investments in security.     

Some algorithms for resource allocation in multiprocessor systems

The paper considers the admissible scheduling with interrupts in a multiprocessor system in the case when directive intervals are specified and program execution times linearly depend on the amounts of allocated resources. A pseudopolynomial algorithm based on reduction of the original problem to the problem of the minimum-cost stream is developed.     

Hierarchical multi-objective decision systems for general resource allocation problems

We consider optimization methods for hierarchical power-decentralized systems composed of a coordinating central system and plural semi-autonomous local systems in the lower level, each of which possesses a decision making unit. Such a decentralized system where both central and local systems possess their own objective function and decision variables is a multi-objective system. The central system allocates resources so as to optimize its own objective, while the local systems optimize their own objectives using the given resources. The lower level composes a multi-objective programming problem, where local decision makers minimize a vector objective function in cooperation. Thus, the lower level generates a set of noninferior solutions, parametric with respect to the given resources. The central decision maker, then, parametric with respect to the given resources. The central decision maker, then, chooses an optimal resource allocation and the best corresponding noninferior solution from among a set of resource-parametric noninferior solutions. A computational method is obtained based on parametric nonlinear mathematical programming using directional derivatives. This paper is concerned with a combined theory for the multi-objective decision problem and the general resource allocation problem.The authors are indebted to Professor G. Leitmann for his valuable comments and suggestions.     

Optimal resource allocation for multiqueue systems with a shared server pool

We study optimal allocation of servers for a system with multiple service facilities and with a shared pool of servers. Each service facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker can dynamically allocate servers to each facility, where adding more servers results in faster processing speeds but against higher utilization costs. The objective is to dynamically allocate the servers over the different facilities such that the sojourn-time constraints are met at minimal costs. This situation occurs frequently in practice, for example, in Grid systems for real-time image processing (iris scans, fingerprints). We model this problem as a Markov decision process and derive structural properties of the relative value function. These properties, which are hard to derive for multidimensional systems, give a full characterization of the optimal policy. We demonstrate the effectiveness of these policies by extensive numerical experiments.     

An optimal maintenance policy for repairable systems with delayed repairs

This work considers a combined maintenance strategy in which the repair of the system failures is performed only in an interval of time of the working period. The objective of this paper is to find the optimal interval in which the repairs can be performed.     

Structural properties of optimal schedules with preemption

Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions. When does an optimal schedule exist (provided that there are feasible schedules)? When does it have a finite/polynomial number of interruptions? Do they occur at integral/rational points only? These theoretical questions are also of practical interest, since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we answer some of these basic questions for a rather general scheduling model (including, as the special cases, the classicalmodels such as parallelmachine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of the objective functions including nearly all known. For some two special cases of objective functions (including, however, all classical ones), we prove the existence of an optimal solution with a special “rational structure.” An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP.     

Analytical form of optimal control and reachability sets in a resource allocation problem

This article investigates a resource allocation problem with a clear economic interpretation. The process dynamics is described in terms of a linear production function. An optimal solution of the control problem is constructed in analytical form. Equal and different positive depreciation rates are considered. The optimal solution is obtained by Pontryagin's maximum principle, which provides a methodologically interesting approach. An alternative approach based on a special representation of the functional is also considered. The reachability set is constructed assuming equal depreciation rates for the controlled plant. An explicit analytical expression is obtained for the optimal value of the functional in terms of the problem parameters. This expression is useful for future analysis. __________ Translated from Prikladnaya Matematika i Informatika, No. 27, pp. 80–99, 2007.     

Ordinal optimization based metaheuristic algorithm for optimal inventory policy of assemble-to-order systems

Assemble-to-order (ATO) systems refer to a manufacturing process in which a customer must first place an order before the ordered item is manufactured. An ATO system that operates under a continuous-review base-stock policy can be formulated as a stochastic simulation optimization problem (SSOP) with a huge search space, which is known as NP-hard. This work develops an ordinal optimization (OO) based metaheuristic algorithm, abbreviated to OOMH, to determine a near-optimal design (target inventory level) in ATO systems. The proposed approach covers three main modules, which are meta-modeling, exploration, and exploitation. In the meta-modeling module, the extreme learning machine (ELM) is used as a meta-model to estimate the approximate objective value of a design. In the exploration module, the elite teaching-learning-based optimization (TLBO) approach is utilized to select N candidate designs from the entire search space, where the fitness of a design is evaluated using the ELM. In the exploitation module, the sequential ranking-and-selection (R&S) scheme is used to optimally allocate the computing resource and budget for effective selecting the critical designs from the N candidate designs. Finally, the proposed algorithm is applied to two general ATO systems. The large ATO system comprises 12 items on eight products and the moderately sized ATO system is composed of eight items on five products. Test results that are obtained using the OOMH approach are compared with those obtained using three heuristic methods and a discrete optimization-via-simulation (DOvS) algorithm. Analytical results reveal that the proposed method yields solutions of much higher quality with a much higher computational efficiency than the three heuristic methods and the DOvS algorithm.     

An optimal repair policy for systems with a limited number of repairs

Traditionally in reliability literature, the repair facilities are always available. This work considers a more general case in which the repair facilities are not always available, but are available only until a fixed number of repairs have been completed. Different assumptions are made to analytically determine an optimal repair policy maximizing the expected reward.     

An optimal statistical testing policy for software reliability demonstration of safety-critical systems

When software reliability demonstration of safety-critical systems by statistical testing is treated as a Test, Analyse and Fix (TAAF) process, an optimal testing policy can be found, which maximises the probability of success of the whole process, over a pre-determined period of time. The optimisation problem is formulated, solved by stochastic dynamic programming, and demonstrated by two numerical examples.     

Approximation algorithms for dynamic resource allocation

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility.     

A resource allocation queueing fairness measure: properties and bounds

Fairness is an inherent and fundamental factor of queue service disciplines in a large variety of queueing applications, ranging from airport waiting lines to computer queueing systems. We study a newly proposed measure, a Resource Allocation Queueing Fairness Measure (RAQFM), first introduced in Raz, Levy, and Avi-Itzhak (Perform. Eval. Rev. 32(1):130–141, 2004). We analyze the properties of RAQFM and tie them to intuition, provide bounds for its values, and discuss briefly how it yields to analysis. This work was supported in part by the Israeli Ministry of Science and Technology, grant number 380-801, and by EURO-NGI network of excellence.     

An optimal maintenance policy for skipping imminent preventive maintenance for systems experiencing random failures

In this study we investigate systems that experience random failures and establish decision rules for performing renewal maintenance; that is, a preventive replacement (PR) policy. We seek a policy that is both simple to execute from the point of view of the maintenance planner but also a policy that is an improvement on existing schemes. We show that our policy is a hybrid of traditional time-based and age-based schemes and one that yields considerable cost savings. Our hybrid policy involves two decision variables. One decision variable is the time between PRs. Hence, for the maintenance planner, the times at which PRs are performed are chronologically fixed. Random failures can occur, however, and the machine receives an emergency renewal (ER) at these times. Hence, within these chronological times, a second decision time is identified. Should an ER occur between the start of a cycle and this second decision time, then the planned PR would still be performed at the end of the cycle. However, if the first ER occurs after this second decision time, then the PR at the end of the cycle is skipped over and the next planned PR would take place at the end of the subsequent cycle. With this simple mechanism, PRs that follow on too closely after an ER are avoided, thus saving the unnecessary expense. Numerical examples are given to examine the validity of the model, using four different failure density functions, namely Weibull, normal, uniform, and negative exponential.     

Centralized resource allocation for enhanced Russell models

This paper proposes a centralized resource allocation (CRA) model for the enhanced Russell model. All the DMUs can be easily projected onto the efficient frontier by solving only one model. This projection can be made by transforming the proposed model to a linear programming problem. In this paper, instead of non-radially increasing or decreasing the inputs or outputs individually, we increase or decrease non-radially all of the inputs and outputs at the same time. By solving a single model, we can provide targets for all DMUs. By the proposed approximation, different targets can be found for all DMUs, as compared to those obtained by the previous approximations. The proposed model can be developed to CRA models. Finally, an applied example emphasizes the importance of the proposed model.     

Pre-processing techniques for resource allocation in the heterogeneous case

The Heterogeneous Resource Allocation Problem (HRAP) deals with the allocation of resources, whose units do not all share the same characteristics, to an established plan of activities. Each activity requires one or more units of each resource which possess particular characteristics, and the objective is to find the minimum number of resource units of each type, necessary to carry out all the activities within the plan, in such a way that two activities whose processing overlaps in time do not have the same resource unit assigned. The HRAP is an NP-Complete problem and it is possible to optimally solve medium-sized HRAP instances in a reasonable time. The objective of this work is to develop pre-processing techniques that enable an HRAP to be transformed into an equivalent HRAP of smaller size, thus increasing the size of HRAPs that can be solved exactly.     

An efficient algorithm for the parametric resource allocation problem

The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter λ, Σ_{i = 1}ⁿ (ƒ_i(x_i + λg_i(x_i)), under simple constraints Σ_{i = 1}ⁿ x_i = M, l_i≤x_i≤u_i and x_i: nonnegative integers for i = 1, 2, …, n, where M is a given positive integer, and l_i and u_i are given lower and upper bounds on x_i. This paper presents an efficient algorithm for computing the sequence of all optimal solutions when λ is continuously changed from 0 to ∞. The required time is O(G√Mlog² n + n log n + n log(M/n)), where G = Σ_{i = 1}ⁿ u_i − Σ_{i = 1n} l_i and an evaluation of ƒ_i(·) or g_i(·) is assumed to be done in constant time.     

On optimal service capacity allocation policy in an advance selling environment in continuous time

Based on some general reasonable assumptions, this paper employs the techniques of calculus of variations and optimal control theory to derive 10 main propositions associated with a service provider who aims at maximizing the present value of revenues/profits over a planning horizon in continuous time. Employing an aggregate pricing-response function that is dependent on excess capacity and a convex service cost formulation, the results show that (i) for a zero discount rate and unanticipated competitive entry, units of service capacity are allocated evenly over time, (ii) for a zero discount rate and anticipated competitive entry, units of allocated service capacity are increasing over time, (iii) for a positive discount rate and unanticipated competitive entry, units of allocated service capacity are decreasing over time, and (iv) for a positive discount rate and anticipated competitive entry, units of allocated service capacity are increasing over time, or are decreasing at first then increasing later. In addition, the questions of how deep a service firm should advance sell, whether advance selling is optimal in continuous time, and whether excess capacity could be an optimal strategy have been addressed. Furthermore, related sensitivity analyses are performed and endpoint constraints together with alternative shapes of the service-cost function are discussed. The managerial implications of the study’s results have been demonstrated.