A new two-party bargaining mechanism

If resources and facilities from different partners need to be engaged for a large-scale project with a huge number of tasks, any of which is indivisible, decision on the number of tasks assigned to any collaborating partner often requires a certain amount of coordination and bargaining among these partners so that the ultimate task allocation can be accepted by any partner in a business union for the project. In the current global financial crisis, such cases may appear frequently. In this paper, we first investigate the behavior of such a discrete bargaining model often faced by service-based organizations. In particular, we address the general situation of two partners, where the finite Pareto efficient (profit allocation) set does not possess any convenient assumption for deriving a bargaining solution, namely a final profit allocation (corresponding to a task assignment) acceptable to both partners. We show that it is not appropriate for our discrete bargaining model to offer the union only one profit allocation. Modifying the original optimization problem used to derive the Nash Bargaining Solution (NBS), we develop a bargaining mechanism and define a related bargaining solution set to fulfil one type of needs on balance between profit-earning efficiency and profit-earning fairness. We then show that our mechanism can also suit both Nash’s original concave bargaining model and its continuous extension without the concavity of Pareto efficient frontier on profit allocation.     

A general space-time model for combinatorial optimization problems (and not only)

We consider the problem of defining a strategy consisting of a set of facilities taking into account also the location where they have to be assigned and the time in which they have to be activated. The facilities are evaluated with respect to a set of criteria. The plan has to be devised respecting some constraints related to different aspects of the problem such as precedence restrictions due to the nature of the facilities. Among the constraints, there are some related to the available budget. We consider also the uncertainty related to the performances of the facilities with respect to considered criteria and plurality of stakeholders participating to the decision. The considered problem can be seen as the combination of some prototypical operations research problems: knapsack problem, location problem and project scheduling. Indeed, the basic brick of our model is a variable x_ilt which takes value 1 if facility i is activated in location l at time t, and 0 otherwise. Due to the conjoint consideration of a location and a time in the decision variables, what we propose can be seen as a general space-time model for operations research problems. We discuss how such a model permits to handle complex problems using several methodologies including multiple attribute value theory and multiobjective optimization. With respect to the latter point, without any loss of the generality, we consider the compromise programming and an interactive methodology based on the Dominance-based Rough Set Approach. We illustrate the application of our model with a simple didactic example.     

A solution framework for the multi-mode resource-constrained cross-dock scheduling problem

In this paper we propose a framework for shift-level container scheduling and resource allocation decisions at a cross-dock facility. The Multi-Mode Resource-Constrained Cross-Dock Scheduling Problem (MRCDSP) approach minimizes material flow and schedules inbound and outbound containers to dock-doors such that the total processing time is minimized subject to the resource constraints at the cross-dock. While container scheduling and resource allocation problems at cross-dock facilities have been studied previously in isolation, our work is the first to consider a complete view of cross-dock operations providing optimal container to dock-door allocation, and a makespan minimizing schedule of containers to the cross-dock. We present a comprehensive framework that includes identification of container clusters to reduce the problem size, a container-to-dock-door assignment algorithm, and a container clusters scheduling model that is solvable for practically sized problems. In a comparative numeric study based on data simulating a cross-dock facility, our approach is shown to outperform current practice, reducing the average time required for processing a set of containers by 37% and reducing the weighted-distance material traveled within the cross-dock by 45%.     

Heuristic Procedures for Practical-Sized Uncapacitated Location-Capacitated Routing Problems*

Facility location and vehicle routing are two important logistical problems closely interrelated in many real-world applications where locating facilities and determining the associated multi-stop vehicle routes are required simultaneously. Previous research has found that using the classical facility location models on these location-routing problems (LRPs) may lead to suboptimal solutions. We propose an approximate approach for the LRPs, which first generates and improves feasible location/allocation schemes with the associated multi-stop routing costs approximated using some route length estimators. We then design the minimum-cost routes based on the location/allocation results. We review two estimators that can provide accurate approximations to the multi-stop route distances; define the uncapacitated location-capacitated routing problem; and evaluate several heuristic procedures for approximately solving the problem. Computational results show that when vehicle capacities are not too restrictive, the sequential procedures that incorporate the two robust route length estimators can produce good solutions to practical-sized problems with a reasonable amount of computational efforts.     

Market‐Based Allocation with Indivisible Bids

We study multiunit double auctions accepting bids with indivisibility constraints. Modeling the auction problem as a Multiple Choice Knapsack Problem and using dynamic programming, we show that incremental computations during bid processing can speed the handling of key auction operations such as clearing and quoting. We propose different price‐quote policies and study their influence on the efficiency of market‐based allocation. Using a reconfigurable manufacturing scenario where agents trade large quantities of multiple goods, we demonstrate potential benefits of supporting indivisibility constraints in bidding. These benefits are highly sensitive to the form of price quote provided, indicating interesting tradeoffs in communication and allocation efficiency.     

On some geometric problems of color-spanning sets

In this paper we study several geometric problems of color-spanning sets: given n points with m colors in the plane, selecting m points with m distinct colors such that some geometric properties of the m selected points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, the planar smallest minimum spanning tree, the planar largest minimum spanning tree and the planar smallest perimeter convex hull. We propose an O(n ^1+ε ) time algorithm for the maximum diameter color-spanning set problem where ε could be an arbitrarily small positive constant. Then, we present hardness proofs for the other problems and propose two efficient constant factor approximation algorithms for the planar smallest perimeter color-spanning convex hull problem.     

An exact method for shrinking pivot tables

Pivot tables are one of the most popular tools for data visualization in both business and research applications. Although they are in general easy to use, their comprehensibility becomes progressively lower when the quantity of cells to be visualized increases (i.e., information flooding problem). Pivot tables are largely adopted in OLAP, the main approach to multidimensional data analysis. To cope with the information flooding problem in OLAP, the shrink operation enables users to balance the size of query results with their approximation, exploiting the presence of multidimensional hierarchies. The only implementation of the shrink operator proposed in the literature is based on a greedy heuristic that, in many cases, is far from reaching a desired level of effectiveness.In this paper we propose a model for optimizing the implementation of the shrink operation which considers two possible problem types. The first type minimizes the loss of precision ensuring that the resulting data do not exceed the maximum allowed size. The second one minimizes the size of the resulting data ensuring that the loss of precision does not exceed a given maximum value. We model both problems as set partitioning problems with a side constraint. To solve the models we propose a dual ascent procedure based on a Lagrangian pricing approach, a Lagrangian heuristic, and an exact method. Experimental results show the effectiveness of the proposed approaches, that is compared with both the original greedy heuristic and a commercial general-purpose MIP solver.     

Multimodal hub location and hub network design

Through observations from real life hub networks, we introduce the multimodal hub location and hub network design problem. We approach the hub location problem from a network design perspective. In addition to the location and allocation decisions, we also study the decision on how the hub networks with different possible transportation modes must be designed. In this multimodal hub location and hub network design problem, we jointly consider transportation costs and travel times, which are studied separately in most hub location problems presented in the literature. We allow different transportation modes between hubs and different types of service time promises between origin–destination pairs while designing the hub network in the multimodal problem. We first propose a linear mixed integer programming model for this problem and then derive variants of the problem that might arise in certain applications. The models are enhanced via a set of effective valid inequalities and an efficient heuristic is developed. Computational analyses are presented on the various instances from the Turkish network and CAB data set.     

Dispatching design for storage-centric wireless sensor networks

In a large-scale storage-centric wireless sensor network (SWSN) where data from different clusters are archived at distributed storage nodes, the dispatching design problem is to determine one or multiple storage nodes for each cluster. To achieve high data fidelity in SWSNs, the dispatching design should aim to reduce the data loss due to the network congestion and, at the same time, to prolong the network lifetime by avoiding sending excessive traffic to some particular storage nodes in order to achieve energy consumption balance among the relaying sensors around the storage node. In this paper, we propose an h-peak dispatching design for SWSN. Under such a design, regular traffic volume from each cluster will receive guaranteed data fidelity, and over-expectation traffic will receive best-effort data fidelity. We use an h-peak model to characterize the traffic deviation which assumes that at most h clusters may have over-expectation traffic simultaneously at a storage node. By incorporating h into the dispatching decision rather than assuming that all clusters may reach their traffic spikes simultaneously, the proposed h-peak dispatching design can achieve high data fidelity in SWSNs.     

Allocating a fixed cost based on data envelopment analysis and satisfaction degree

This paper uses the Data Envelopment Analysis (DEA) technique to solve the problem of allocating a fixed cost across a set of comparable decision making units (DMUs) in a fair way. It first investigates the effect of the fixed cost on each DMU and on the collection of DMUs. Next we prove that there exist some cost allocations which can make each DMU and the collection of DMUs efficient. We show that such a cost allocation is unique and equivalent to the proportional sharing method if the fixed cost allocation problem is a one-dimensional case. In a multidimensional case, the fixed cost allocations may not be unique. This paper defines the concept of satisfaction degree, and proposes a maxmin model and a corresponding algorithm to generate a unique fixed cost allocation. Finally, the proposed approach has been applied to a data set from prior literature.     

Maximizing target-temporal coverage of mission-driven camera sensor networks

In camera sensor networks (CSNs), the target coverage problem is of special importance since a sensor with different viewing directions captures distinct views for the same target. Furthermore, mission-driven monitoring applications in CSNs usually have special network lifetime requirements in which the limited battery lifetime of sensors probably can not sustain for full coverage. In this paper, based on effective-sensing model, we address three new coverage problems in mission-driven camera sensor networks, namely the target-temporal effective-sensing coverage with non-adjustable cameras (TEC-NC) problem, the target-temporal effective-sensing coverage with adjustable cameras (TEC-AC) problem, and the target-temporal effective-sensing coverage with fully-adjustable cameras (TEC-FAC) problem. Given a mission period, the common objective of the problems is to find a sleep-wakeup schedule such that the overall target-temporal coverage is maximized. For TEC-NC, we propose a 2-approximation algorithm and two new heuristics. We also design two greedy strategies, each of which can be combined with our solutions for TEC-NC to deal with TEC-AC and TEC-FAC, respectively. We finally conduct extensive experiments to evaluate the performance of the proposed algorithms, whose results indicate the proposed algorithms outperform the existing alternatives as well as are close to the theoretical optimum on average under certain conditions.     

基于DNA遗传算法的表面贴装生产线负荷优化分配

印制电路板组装任务的负荷优化分配包含设备约束、工艺约束等大量约束,是电子行业表面贴装生产线中的一类重要优化问题。其优化目标是在生产节拍给定和一定约束条件下,使得不同贴装机负荷均衡,任务分配达到最优。首先,根据不同表面贴装机、不同吸嘴及多种类型元件匹配的的复杂性,提出贴装机任务分配组合优化的问题;然后分析设备和元件的参数、组装可行性、贴装时间,以及贴装优化关系等因素,并提出假设条件,建立了平衡率最大化条件下的负荷分配组合优化的数学模型;最后,针对贴装生产线负荷分配问题的复杂性与特殊性,通过改良编码方式后的DNA遗传算法来优化组合数学模型,计算适应度,并借助MATLAB进行仿真求解,进而找到最优解。结果表明：本文提出的贴装生产线负荷分配方法可以解决带复杂约束的印制电路板组装负荷优化分配问题,提高设备的平衡率和生产效率,促进生产线的优化运行。     

Discrete parallel machine makespan ScheLoc problem

Scheduling–Location (ScheLoc) problems integrate the separate fields of scheduling and location problems. In ScheLoc problems the objective is to find locations for the machines and a schedule for each machine subject to some production and location constraints such that some scheduling objective is minimized. In this paper we consider the discrete parallel machine makespan ScheLoc problem where the set of possible machine locations is discrete and a set of n jobs has to be taken to the machines and processed such that the makespan is minimized. Since the separate location and scheduling problem are both \(\mathcal {NP}\)-hard, so is the corresponding ScheLoc problem. Therefore, we propose an integer programming formulation and different versions of clustering heuristics, where jobs are split into clusters and each cluster is assigned to one of the possible machine locations. Since the IP formulation can only be solved for small scale instances we propose several lower bounds to measure the quality of the clustering heuristics. Extensive computational tests show the efficiency of the heuristics.     

SOLVING A COMBINED PART-SELECTION,MACHINE-LOADING,AND TOOL-CONFIGURATION PROBLEM IN FLEXIBLE MANUFACTURING SYSTEMS*

Loading too many or too few copies of tools may result in waste of tool magazine slots and unnecessary machine shutdowns. This is a consequence of not integrating the tool-configuration problem with other flexible manufacturing system (FMS) planning problems. Solving part-selection, machine-loading and tool-configuration problems independently may cause entire solutions to be infeasible. We propose both an approach to the explicit formulation of tool configuration problems and the simultaneous solution of part-selection, machine-loading and tool-configuration problems. We developed and solved sequentially some associated bicriteria models sequentially. We also discussed the effects of considering some secondary objectives on system performance and described the concepts of critical magazine size and critical machining time using an example problem. Unnecessary allocation and under-use of tool magazine capacity and machining time could be reduced by considering the critical magazine size and machining time. Finally, we suggest using a method based on Lagrangian relaxation for solving large size problems.     

Linear solution schemes for Mean-SemiVariance Project portfolio selection problems: An application in the oil and gas industry

We study the Mean-SemiVariance Project (MSVP) portfolio selection problem, where the objective is to obtain the optimal risk-reward portfolio of non-divisible projects when the risk is measured by the semivariance of the portfolio׳s Net-Present Value (NPV) and the reward is measured by the portfolio׳s expected NPV. Similar to the well-known Mean-Variance portfolio selection problem, when integer variables are present (e.g., due to transaction costs, cardinality constraints, or asset illiquidity), the MSVP problem can be solved using Mixed-Integer Quadratic Programming (MIQP) techniques. However, conventional MIQP solvers may be unable to solve large-scale MSVP problem instances in a reasonable amount of time. In this paper, we propose two linear solution schemes to solve the MSVP problem; that is, the proposed schemes avoid the use of MIQP solvers and only require the use of Mixed-Integer Linear Programming (MILP) techniques. In particular, we show that the solution of a class of real-world MSVP problems, in which project returns are positively correlated, can be accurately approximated by solving a single MILP problem. In general, we show that the MSVP problem can be effectively solved by a sequence of MILP problems, which allow us to solve large-scale MSVP problem instances faster than using MIQP solvers. We illustrate our solution schemes by solving a real MSVP problem arising in a Latin American oil and gas company. Also, we solve instances of the MSVP problem that are constructed using data from the PSPLIB library of project scheduling problems.     

Generalized Steiner Problems and Other Variants

In this paper, we examine combinatorial optimization problems by considering the case where the set N (the ground set of elements) is expressed as a union of a finite number of m nonempty distinct subsets N ₁,...,N _m. The term we use is the generalized Steiner problems coined after the Generalized Traveling Salesman Problem. We have collected a short list of classical combinatorial optimization problems and we have recast each of these problems in this broader framework in an attempt to identify a linkage between these “generalized” problems. In the literature one finds generalized problems such as the Generalized Minimum Spanning Tree (GMST), Generalized Traveling Salesman Problem (GTSP) and Subset Bin-packing (SBP). Casting these problems into the new problem setting has important implications in terms of the time effort required to compute an optimal solution or a “good” solution to a problem. We examine questions like “is the GTSP “harder” than the TSP?” for a number of paradigmatic problems starting with “easy” problems such as the Minimal Spanning Tree, Assignment Problem, Chinese Postman, Two-machine Flow Shop, and followed by “hard” problems such as the Bin-packing, and the TSP.     

Intra-Organizational and inter-organizational resource allocation in two-stage network systems

There are organizational systems, such as bank branches and two-stage supply chains, which are composed of multiple parallel two-stage structures. Resource allocation in these systems is to maximize the benefit of the overall organization from a global viewpoint. In this study, we consider two types of systems at an organizational level: a centralized organizational system treating the whole two-stage production process as a basic unit, and a decentralized organizational system including two sub-organizations (groups) treating one of the two-stage production processes as a basic unit. We propose intra-organizational and inter-organizational resource allocation plans for two different organizational systems, respectively. Specially, two modes of free intermediate resource allocation (Free IRA) and fixed intermediate resource allocation (Fixed IRA) are discussed for the decentralized organizational system. The proposed allocation plans are based on two-stage data envelopment analysis models with bi-level formulations, in which the upper-level model is to maximize the entire organizational effectiveness (total outputs minus total inputs) by determining the optimized input resources and output targets while the lower-level model is concerned with efficiency constraints of all decision-making units simultaneously. The developed methods are illustrated by an application to a real-world problem with 17 city bank branches.     

On residual approximation in solution extension problems

The solution extension variant of a problem consists in, being given an instance and a partial solution, finding the best solution comprising the given partial solution. Many problems have been studied with a similar approach. For instance the Pre-Coloring Extension problem, the clustered variant of the Travelling Salesman problem, or the General Routing Problem are in a way typical examples of solution extension variant problems. Motivated by practical applications of such variants, this work aims to explore different aspects around extension on classical optimization problems. We define residue-approximations as algorithms whose performance ratio on the non-prescribed part can be bounded, and corresponding complexity classes. Using residue-approximation, we classify problems according to their residue-approximability, exhibit distinct behaviors and give several examples and first interesting results.     

Generalized symmetric weight assignment technique: Incorporating managerial preferences in data envelopment analysis using a penalty function

In this paper, we generalize the Symmetric Weight Assignment Technique to incorporate all managerial preferences in Data Envelopment Analysis (DEA). This is a method that promotes managerial preferences, while not changing the feasibility region of the nominal DEA model, unlike standard techniques such as cone ratio and assurance region that potentially yield infeasible problems. We discuss how this generalization is motivated by a real word problem where the decision maker's preference is not precisely known. We also discuss how we are using our generalization in solving a workforce allocation problem for the United States Navy.     

Assortment optimisation problem: A distribution-free approach

Assortment optimisation is a critical decision that is regularly made by retailers. The decision involves a trade-off between offering a larger assortment of products but smaller inventories of each product and offering a smaller number of varieties with more inventory of each product. We propose a robust, distribution-free formulation of the assortment optimisation problem such that the assortment and inventory levels can be jointly optimised without making specific assumptions on the demand distributions of each product. We take a max-min approach to the problem that provides a guaranteed lower bound to the expected profit when only the mean and variance of the demand distribution are known. We propose and test three heuristic algorithms that provide solutions in O(nlog (n)) time and identify two cases where one of the heuristics is guaranteed to return optimal policies. Through numerical studies, we demonstrate that one of the heuristics performs extremely well, with an average optimality gap of 0.07% when simulated under varying conditions. We perform a sensitivity analysis of product and store demand attributes on the performance of the heuristic. Finally, we extend the problem by including maximum cardinality constraints on the assortment size and perform numerical studies to test the performance of the heuristics.