Simultaneous Job Scheduling and Resource Allocation on Parallel Machines

Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time of a job is determined internally by the amount of the resources allocated. In these situations, both the cost associated with the job schedule and the cost of the resources allocated should be taken into account. Therefore, job scheduling and resource allocation should be carefully coordinated and optimized jointly in order to achieve an overall cost-effective schedule. In this paper, we study a parallel-machine scheduling model involving both job processing and resource allocation. The processing time of a job is non-increasing with the cost of the allocated resources. The objective is to minimize the total cost including the cost measured by a scheduling criterion and the cost of all allocated resources. We consider two particular problems of this model, one with the scheduling criterion being the total weighted completion time, and the other with that being the weighted number of tardy jobs. We develop a column generation based branch and bound method for finding optimal solutions for these NP-hard problems. The method first formulates the problems as set partitioning type formulations, and then solves the resulting formulations exactly by branch and bound. In the branch and bound, linear relaxations of the set partitioning type formulations are decomposed into master problems and single-machine subproblems and solved by a column generation approach. The algorithms developed based on this method are capable of solving the two problems with a medium size to optimality within a reasonable computational time.     

Single-machine group scheduling with deteriorating jobs and allotted resource

In this paper, we consider single-machine scheduling problems with deteriorating jobs and resource allocation in a group technology environment. In the proposed model of this paper the actual processing time of a job depend on its starting time and the amount of resource allocated to it, and the actual setup time of a group depend on its starting time and the amount of resource allocated. Deterioration effect and two resource allocation functions are examined for minimizing the weighted sum of makespan and total resource cost. For the linear resource allocation function and the convex resource allocation function, we show that the problem remains polynomially solvable under certain conditions.     

Integrated bank performance assessment and management planning using hybrid minimax reference point – DEA approach

The purpose of assessing past performances and setting future targets for an organisation such as a bank branch is to find where the branch stands in comparison to its peers within the bank branch network and how to improve the efficiency of its operations relatively when compared to the best practice branches. However, future performance targets may be set arbitrarily by the head-office and thus could be unrealistic and not achievable by a branch. A hybrid minimax reference point-data envelopment analysis (HMRP-DEA) approach is investigated to incorporate the value judgements of both branch managers and head-office directors and to search for the most preferred solution (MPS) along the efficient frontier for each bank branch. The HMRP-DEA approach is composed of three minimax models, including the super-ideal point model, the ideal point model and the shortest distance model, which share the same decision and objective spaces, are different from each other only in their reference points and weighting schema, and are proven to be equivalent to the output-oriented DEA dual models. These models are examined both analytically and graphically in this paper using a case study, which provides the unprecedented insight into integrated efficiency and trade-off analyses. The HMRP-DEA approach uses DEA as an ex-post-facto evaluation tool for past performance assessment and the minimax reference point approach as an ex-ante planning tool for future performance forecasting and target setting. Thus, the HMRP-DEA approach provides an alternative means for realistic target setting and better resource allocation. It is examined by a detailed investigation into the performance analysis for the fourteen branches of an international bank in the Greater Manchester area.     

Fuzzy network technique for technological forecasting

The stochastic network technique is known to be a powerful tool carrying out a technological forecast of complex systems. A network dealt with is characterized by a tetrad of essential elements: logical nodes with some inputs and outputs, probabilistics activity branches, feedback loops, and multiple sources and sinks. A set of network parameters is defined for each element and their values are estimated for practical analysis of the network. In the case where the system to be treated is very large and/or complex, it cannot always be represented by a definite network and therefore forecasted values of parameters are inevitably indefinite themselves. A conventional probabilistic approach is sometimes inadequate in such a case. In the light of these facts, the paper proposes a fuzzy network technique, in which among activity branches emanating from a node, a branch to be undertaken once the node is realized belongs to a fuzzy set; and the time required to complete an activity branch belongs to a fuzzy set. Operations of maximum and minimum for sum and product of fuzzy sets take the place of manipulations of addition and multiplication for probabilities, respectively. Although the operations are somewhat formal, the obtained results seem interesting. A numerical example is attached to show a comparison of the proposed technique with the conventional one.     

Allocating the fixed cost as a complement of other cost inputs: A DEA approach

In cost allocation problem, traditional DEA approaches allocate the fixed cost among a group of decision making units (DMUs), and treat the allocated cost as an extra input of each DMU. If costs except for the fixed cost are regarded as inputs in the cost allocation problem, then it is obvious that the fixed cost is a complement of other inputs rather than an extra independent input. Therefore it is necessary to combine the allocated cost with other cost measures in cost allocation problem. Based on this observation, this paper investigates the relationship between the allocated cost and the DEA efficiency score and develops a DEA-based approach to allocate the fixed cost among various DMUs. An example of allocating advertising expenditure between a car manufacturer and its dealers is presented to illustrate the method proposed in this paper.     

A generalized DEA model for centralized resource allocation

In this paper, we introduced a new generalized centralized resource allocation model which extends Lozano and Villa’s and Asmild et al.’s models to a more general case. In order to uncover the sources of such total input contraction in the generalized centralized resource allocation model, we applied the structural efficiency to further decompose it into three components: the aggregate technical efficiency, the aggregate allocative efficiency and re-transferable efficiency components. The proposed models are not only flexible enough for the central decision-maker to adjust the inputs and outputs to achieve the total input contraction but also identify the sources of such total input contraction, thereby giving rise to an important interpretation and understanding of the generalized centralized resource allocation model. Finally, an empirical example is used to illustrate the approach.     

基于DEA的二阶段网络系统的固定成本分摊方法

结合DEA和博弈的思想研究二阶段网络系统的固定成本分摊问题,将分摊成本作为新的投入,可以证明存在某种分摊使DMU整体效率达到最优,在此基础上考虑各个DMU之间以及DMU内部之间的博弈,首先建立讨价还价乘积最大化模型,求出各DMU唯一的分摊解,然后建立DMU子系统之间的讨价还价模型,给出子系统的分摊解,最终的分摊方案满足系统效率和子系统效率为1,与现有的方法相比具有一定的优势.     

Fixed cost and resource allocation based on DEA cross-efficiency

In many managerial applications, situations frequently occur when a fixed cost is used in constructing the common platform of an organization, and needs to be shared by all related entities, or decision making units (DMUs). It is of vital importance to allocate such a cost across DMUs where there is competition for resources. Data envelopment analysis (DEA) has been successfully used in cost and resource allocation problems. Whether it is a cost or resource allocation issue, one needs to consider both the competitive and cooperative situation existing among DMUs in addition to maintaining or improving efficiency. The current paper uses the cross-efficiency concept in DEA to approach cost and resource allocation problems. Because DEA cross-efficiency uses the concept of peer appraisal, it is a very reasonable and appropriate mechanism for allocating a shared resource/cost. It is shown that our proposed iterative approach is always feasible, and ensures that all DMUs become efficient after the fixed cost is allocated as an additional input measure. The cross-efficiency DEA-based iterative method is further extended into a resource-allocation setting to achieve maximization in the aggregated output change by distributing available resources. Such allocations for fixed costs and resources are more acceptable to the players involved, because the allocation results are jointly determined by all DMUs rather than a specific one. The proposed approaches are demonstrated using an existing data set that has been applied in similar studies.     

路政应急管理中资源布局的混合整数规划模型

本文根据道路灾害事故的发生特点,对城市路桥养护系统的运行模式和资源的合理调用机理进行分析,考虑到事发地点潜在的资源需求概率,建立资源布局的混合整数规划模型.本模型中资源布局方案的调度决策基础是在灾害事故的资源需求不发生变化的条件下,使得每个救助点的资源同时部分地为辖区内现有事故和潜在事故服务,而现有事故的剩余需求由其他救助点派出资源来满足.该模型的目标是解决城市中因同一时间段内发生两起灾害事故而造成路桥破坏导致的救助资源短缺问题,同时避免资源的闲置浪费.最后,通过算例证明,本方法较通常方法对城市总的资源配置量大大减少.     

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.     

基于收益管理和仿真的第三方仓储资源分配

针对不确定市场需求条件下第三方仓储资源的能力规划与分配问题,构建随机数学规划模型,理论分析证明了最优资源分配量的存在性,并指出最优资源分配量是单位资源成本的递减函数、单位资源收益和单位损失成本的递增函数。鉴于解析求解的复杂性,基于收益管理思想,结合离散事件仿真技术和响应曲面法,提出一种新的分析求解框架:收益管理用于细分顾客、构建资源分配策略,仿真模型刻画系统随机特性并评估系统绩效指标,响应曲面法则优化分配策略并探寻绩效改进方向。案例研究和仿真实验结果显示,根据顾客类别分配仓储能力的策略优于传统的先到先服务策略,收益管理、响应曲面法与仿真的综合集成,能够提高系统收益,从而使本文所提方法体系得到了有效验证。     

Linking customer satisfaction, employee appraisal, and business performance: an evaluation methodology in the banking sector

The linkage among customer satisfaction, employee evaluation, and business performance data is very important in modern business organizations. Several previous research efforts have studied this linkage, focusing mainly on the financial or business performance in order to analyze the efficiency of an organization. However, recent studies have tried to consider other important performance indicators, which are able to affect business operations and future growth (e.g., external and internal customer satisfaction). In the case of the banking industry, studying the relations among the aforementioned variables is able to give insight in the performance evaluation of bank branches and the viability analysis of the banking organization. This paper presents a real-world study for measuring the relative efficiency of a set of bank branches using a Data Envelopment Analysis (DEA) approach. In particular, a multistage DEA network model is proposed, using a set of performance indicators that combine customer satisfaction, employee evaluation, and business performance indices. The main aim of the presented study is to evaluate the relative efficiency of each customer service delivery step, in the environment of a bank branch. The results are also able to estimate the contribution of the assessed performance indicators to the branch’s overall efficiency, and to determine potential improvement actions.     

Network DEA efficiency in input–output models: With an application to OECD countries

We undertake network efficiency analysis within an input–output model that allows us to assess potential technical efficiency gains by comparing technologies corresponding to different economies. Input–output tables represent a network where different sectoral nodes use primary inputs (endowments) to produce intermediate input and outputs (according to sectoral technologies), and satisfy final demand (preferences). Within the input–output framework it is possible to optimize primary inputs allocation, intermediate production and final demand production by way of non-parametric data envelopment analysis (DEA) techniques. DEA allows us to model the different subtechnologies corresponding to alternative production processes, to assess efficient resource allocation among them, and to determine potential output gains if inefficiencies were dealt with. The proposed model optimizes the underlying multi-stage technologies that the input–output system comprises identifying the best practice economies. The model is applied to a set of OECD countries.     

Manpower allocation using genetic annealing

In this paper, we focus on a real size manpower allocation problem. It was modeled after a real world problem of distributing the salesmen force over the branches of a company. The problem includes multiple objectives and the number of salesmen at each branch is unspecified. Conventional integer programming approach and conventional metaheuristics seem to have problems with solving the large size version of this problem. The versatility of our proposed heuristics based on a modification of genetic annealing is exemplified through solving the real size manpower allocation problem. For comparison sake, several small sized versions were solved using our method, conventional integer programming approach, and some well known metaheuristics.     

A linear proportional effort allocation rule

This paper proposes a new class of allocation rules in network games. Like the solution theory in cooperative games of how the Harsanyi dividend of each coalition is distributed among a set of players, this new class of allocation rules focuses on the distribution of the dividend of each network. The dividend of each network is allocated in proportion to some measure of each player’s effort, which is called an effort function. With linearity of the allocation rules, an allocation rule is specified by the effort functions. These types of allocation rules are called linear proportional effort allocation rules. Two famous allocation rules, the Myerson value and the position value, belong to this class of allocation rules. In this study, we provide a unifying approach to define the two aforementioned values. Moreover, we provide an axiomatic analysis of this class of allocation rules, and axiomatize the Myerson value, the position value, and their non-symmetric generalizations in terms of effort functions. We propose a new allocation rule in network games that also belongs to this class of allocation rules.     

Allocative efficiency in branch banking

Bank branch efficiency and organization change is analyzed using data from 50 savings bank branches in Sweden. First, technical and allocative efficiencies are analyzed, using non-priced and priced inputs. Secondly, by grouping the branches according to their organizational designation, efficiency is examined by level of service. Trends in performance over two time periods are also analyzed.     

Fair resource allocation for different scenarios of demands

This paper considers a resource allocation problem, which objective is to treat fairly all the system users. Usually the requests cannot be entirely predicted, but the manager can forecast the request evolution, this leading to a set of possible scenarios. Such a problem arises for instance in network bandwidth allocation as well as in storage space management. It also appears in the management of computer systems, such as computational grids or in cloud computing, when teams share a common pool of machines. Problems of fair resource sharing arise among users with equal access right but with different needs.Here the problem is tackled by a multi-criteria model, where one criterion is associated to one scenario. A solution is a policy, which provides an allocation for each scenario. An algorithm is proposed and analysed that lists all solutions which are Pareto optimal with regard to the different possible user request scenarios. The algorithm is used offline, but can be adapted, with some additional hypothesis, to be used online.     

Multi-objectives Tabu Search based algorithm for progressive resource allocation

Military course of action planning involves time and space synchronization as well as resource and asset allocation. A mission could be seen as a defined set of logical ordered tasks with time and space constraints. The resources to task rules require that available assets should be allocated to each task. A combination of assets might be required to execute a given task. The couple (task, resources) constitutes an action. This problem is formulated as a multi-objectives scheduling and resource allocation problem. Any solution is assessed based on a number of conflicting and heterogeneous objectives. In fact, military planning officers should keep perfecting the plan based on the Commander’s criteria for success. The scheduling problem and resource allocation problem are considered as NP-Hard Problems [A. Guitouni, B. Urli, J.-M. Martel, Course of action planning: A project based modelling, Working Paper, Faculté des sciences de l’ administration, Université Laval, Québec, 2005]. This paper is concerned with the multi-objectives resource allocation problem. Our objective is to find adequate resource allocation for given courses of action schedule. To optimize this problem, this paper investigates non-exact solution methods, like meta-heuristic methods for finding potential efficient solutions. A progressive resource allocation methodology is proposed based on Tabu Search and multi-objectives concepts. This technique explores the search space so as to find a set of potential efficient solutions without aggregating the objectives into a single objective function. It is guided by the principle of maximizing the usage of any resource before considering a replacement resource. Thus, a given resource is allocated to the maximum number of tasks for a given courses of action schedule. A good allocation is a potential efficient solution. These solutions are retained by applying a combination of a dominance rule and a multi-criteria filtering method. The performance of the proposed Pareto-based approach is compared to two aggregation approaches: weighted-sum and the lexicographic techniques. The result shows that a Pareto-based approach is providing better solutions and allowing more flexibility to the decision-maker.     

EFFICIENT MANAGEMENT OF GROUNDWATER QUALITY

This work develops a theoretical framework that considers the pollution transport in groundwater in an optimization of social benefits from a groundwater resource, and provides a spatial and temporal allocation of the use of contaminating inputs. A space dependent social cost function is constructed, taking into account factors such as the wells' locations and emitting firms' locations, in addition to profits from polluting activities. The social optimization is formulated using the pollution concentrations as state variables and the pollution transport as state dynamics. This optimization yields a spatially differentiated shadow price which leads to optimal policy which is nonuniform in general, and uniform only for special cases.     

A global optimization algorithm for reliable network design

In this paper, we consider the problem of designing reliable networks that satisfy supply/demand, flow balance, and capacity constraints, while simultaneously allocating certain resources to mitigate the arc failure probabilities in such a manner as to minimize the total cost of network design and resource allocation. The resulting model formulation is a nonconvex mixed-integer 0-1 program, for which a tight linear programming relaxation is derived using RLT-based variable substitution strategies and a polyhedral outer-approximation technique. This LP relaxation is subsequently embedded within a specialized branch-and-bound procedure, and the proposed approach is proven to converge to a global optimum. Various alternative partitioning strategies that could potentially be employed in the context of this branch-and-bound framework, while preserving the theoretical convergence property, are also explored. Computational results are reported for a hypothetical scenario based on different parameter inputs and alternative branching strategies. Related optimization models that conform to the same class of problems are also briefly presented.