Search

Not only the expertise of people but also the collaboration among people are of great importance for a team. Given a set of experts with different skills, a social network that reflects the collaboration among people and a task, the team formation problem in social networks aims at forming a team to complete the task. The team is required to satisfy the skill requirements of the task and collaborates efficiently. Different communication cost functions have been proposed to have a good measure on the collaboration strength of a team in the existing work. However, the grouped organization structure inside team is never considered, which is very common in real life scenarios. In a grouped team, we are more concerned with the collaboration among people in same group and among leaders. In this paper, a novel communication cost function for a grouped team is proposed, and we define the Grouped Team Formation problem. To solve the problem, an exact algorithm is proposed. We further modify the exact algorithm to propose two heuristic algorithms with higher efficiency. Extensive experiments evaluate the effectiveness and efficiency of the proposed methods, and validate the reasonability of our problem definition in practical settings. [ABSTRACT FROM AUTHOR]

Automated design methods facilitate the study of the influence of design forms on the buildings' behavior, and help compare the performance of alternative designs more effectively. This paper presents a Unified Matrix Method, as an effective automated method that aids in the search for the best compromised spatial design of multi-story modular buildings during the early stages of the design process. The method is presented in a general format employing a balanced approach that integrates different design aspects together, namely constructional, architectural and structural aspects. First, it describes how the spatial design of multi-story modular buildings can be generally represented by three-dimensional matrices arisen from combinatorial problems. Then, the spatial design is modeled by a design structure matrix, which decomposes the building into smaller components such as modular units, connections, stabilizing and bracing systems. Finally, a three-dimensional assignment problem is formulated to solve the problem. Particular conditions or preferences for the spatial design can be incorporated as constraints on the assignment problem. In order to show the robustness of the method, an actual case study is designed and employed, with the aim of obtaining a spatial design having minimum construction cost, maximum plan regularity and maximum energy efficient form. [ABSTRACT FROM AUTHOR]

This paper presents a multi-objective assignment problem (MAP) with interval parameters. Here, the model concentrates on three criteria: total cost, total profit and total operation time of assignment. The proposed model is classified as a nonlinear programming, in which it is difficult to solve. Hence, the model is converted into crisp linear programming problem by applying a substitution variables approach. In addition, a weighted min-max method is applied to transform the multi-objective problem into a single objective optimization problem. Finally, several numerical examples are provided to illustrate the implementation of the proposed approach. The results clearly provide some evidences that the proposed approach was easier to contrast compared with other approaches. The results also indicate that decision makers’ preferences over various objectives could influence on solutions.

Discrete combinatorial optimization problems in real world are typically defined via an ensemble of potentially high dimensional measurements pertaining to all subjects of a system under study. We point out that such a data ensemble in fact embeds with system's information content that is not directly used in defining the combinatorial optimization problems. Can machine learning algorithms extract such information content and make combinatorial optimizing tasks more efficient? Would such algorithmic computations bring new perspectives into this classic topic of Applied Mathematics and Theoretical Computer Science? We show that answers to both questions are positive. One key reason is due to permutation invariance. That is, the data ensemble of subjects' measurement vectors is permutation invariant when it is represented through a subject-vs-measurement matrix. An unsupervised machine learning algorithm, called Data Mechanics (DM), is applied to find optimal permutations on row and column axes such that the permuted matrix reveals coupled deterministic and stochastic structures as the system's information content. The deterministic structures are shown to facilitate geometry-based divide-and-conquer scheme that helps optimizing task, while stochastic structures are used to generate an ensemble of mimicries retaining the deterministic structures, and then reveal the robustness pertaining to the original version of optimal solution. Two simulated systems, Assignment problem and Traveling Salesman problem, are considered. Beyond demonstrating computational advantages and intrinsic robustness in the two systems, we propose brand new robust optimal solutions. We believe such robust versions of optimal solutions are potentially more realistic and practical in real world settings.

We proposed and created a methodology to solve a real-world problem, which is a special case of the generalized assignment problem. The problem consists of assigning drivers to harvesters, which will then be assigned to harvest sugarcane in order to maximize daily profit. A set of drivers have various levels of experience. Therefore, a different capability to harvest sugarcane leads to a range of daily wages. Each harvester has different operating years and engine size, which affects its fuel consumption rate and capacity to harvest sugarcane, respectively. Assigning a worker to a harvester can improve the fuel consumption and efficiency of the harvester. We developed a mathematical model to reflect this problem and to solve it to find the maximum outcome using Lingo v.11 commercial optimization software. Since Lingo v.11 is limited to solving only small-size test instances, for medium to large test instances, four modified differential evolution (MDE) algorithms were used to solve the problem: MDE-1, MDE-2, MDE-3, and MDE-4. MDE-2 was found to be the best proposed heuristics because it has intensification and diversification ability. MDE has been tested with the case study. We tried to increase the daily profit by implementing three strategies: (1) change all harvesters that are more than five years old, (2) train drivers to reach maximum capacity, and (3) a combination of 1 and 2. Each strategy has a different investment. The breakeven point (number of days) to return the investment was calculated from the increase of daily profit. The computational results show that strategy 2 is the best because it has the quickest rate of investment return rate. However, this strategy has a disadvantage, since it is possible that drivers may leave the company if they have been highly trained. Moreover, strategy 1 has an acceptable break-even point at 392 days.

This article presents algorithms for solving a special case of the vehicle routing problem (VRP). We define our proposed problem of a special VRP case as a combination of two hard problems: the generalized assignment and the vehicle routing problem. The different evolution (DE) algorithm is used to solve the problem. The recombination process of the original DE is modified by adding two more sets of vectors—best vector and random vector—and using two other sets—target vector and trial vector. The linear probability formula is proposed to potentially use one out of the four sets of vectors. This is called the modified DE (MDE) algorithm. Two local searches are integrated into the MDE algorithm: exchange and insert. These procedures create a DE and MDE that use (1) no local search techniques, (2) two local search techniques, (3) only the exchange procedure, and (4) only the insert procedure. This generates four DE algorithms and four MDE algorithms. The proposed methods are tested with 15 tested instances and one case study. The current procedure is compared with all proposed heuristics. The computational result shows that, in the case study, the best DE algorithm (DE-4) has a 1.6% better solution than that of the current practice, whereas the MDE algorithm is 8.2% better. The MDE algorithm that uses the same local search as the DE algorithms generates a maximum 5.814% better solution than that of the DE algorithms.

This study aims to solve the real-world multistage assignment problem. The proposed problem is composed of two stages of assignment: (1) different types of trucks are assigned to chicken farms to transport young chickens to egg farms, and (2) chicken farms are assigned to egg farms. Assigning different trucks to the egg farms and different egg farms to the chicken farms generates different costs and consumes different resources. The distance and the idle space in the truck have to be minimized, while constraints such as the minimum number of chickens needed for all egg farms and the longest time that chickens can be in the truck remain. This makes the problem a special case of the multistage assignment (S-MSA) problem. A mathematical model representing the problem was developed and solved to optimality using Lingo v.11 optimization software. Lingo v.11 can solve to optimality only small- and medium-sized test instances. To solve large-sized test instances, the differential evolution (DE) algorithm was designed. An excellent decoding method was developed to increase the search performance of DE. The proposed algorithm was tested with three randomly generated datasets (small, medium, and large test instances) and one real case study. Each dataset is composed of 12 problems, therefore we tested with 37 instances, including the case study. The results show that for small- and medium-sized test instances, DE has 0.03% and 0.05% higher cost than Lingo v.11. For large test instances, DE has 3.52% lower cost than Lingo v.11. Lingo v.11 uses an average computation time of 5.8, 103, and 4320 s for small, medium and large test instances, while DE uses 0.86, 1.68, and 8.79 s, which is, at most, 491 times less than Lingo v.11. Therefore, the proposed heuristics are an effective algorithm that can find a good solution while using less computation time.

The article investigates the problem of task assignment of vehicles for a production company. The presented problem is a complex decision-making issue which has not been analyzed in the literature before. Two stages must be passed through in order to solve the task assignment problem of the vehicles for the production company. The first stage is to designate the tasks, the other one is to determine the number of the vehicles that is needed to perform these tasks. The task in the analyzed problem is defined as transporting the cargo from the suppliers to the warehouses and from the warehouses to the production company. The number of the tasks depends on the type of the vehicle which carries out a given task. In order to solve the presented problem, the mathematical model has been developed, i.e., decision variables, constraints, and criterion functions. There are three types of decision variables occurring in the model, which means that this problem is quite complex. The first type of the decision variables determines the volume of the cargo which flows among the facilities on a given working day, the second type of the decision variables determines the use of a given type of the vehicle in the task, and the third type of the decision variables determines the number of the vehicles which perform the task. The criterion functions take the following form: the fuel consumption costs, the transition costs of the cargo via the warehouses, the purchase costs of the cargo, and the task completion time. In order to solve the task assignment problem of the vehicles, a genetic algorithm has been developed. The proposed method of task assignment solution is unique due to the coding method of individuals and related recombination procedures. The construction stages of this algorithm are presented. The algorithm has been verified by the use of the real input data. The developed model and method of its solution are unique in the application to the service of manufacturing enterprises. Due to the high efficiency and multi-aspect approach, it can be applied in enterprises of various industries as support for decision-makers in the optimization of resources.

We describe a project of an exact parallel algorithm for traveling salesman problems (TSPs) of large sizes. It is based on the algorithm developed by E. Balas and N. Christofides almost 40 years ago. Balas’ and Christofides’ algorithm uses branch-and-bound, Hungarian algorithm for assignment problem, and several heuristics to effectively eliminate unnecessary branches of the solution tree. We propose several modifications (including parallelization) of the simplified version of their algorithm which should improve its performance. The modified algorithm was implemented in C++ with OpenMP and tested on graphs with around 1000 nodes. Computational results indicate a possibility of getting exact solutions of TSPs with 10000 nodes in minutes. New heuristic algorithms could be derived from the exact algorithm to solve even bigger problems. Such algorithms could be applied to genome assembly. [ABSTRACT FROM AUTHOR]

We study a multi-stage dynamic assignment interdiction (DAI) game in which two agents, a user and an attacker, compete in the underlying bipartite assignment graph. The user wishes to assign a set of tasks at the minimum cost, and the attacker seeks to interdict a subset of arcs to maximize the user's objective. The user assigns exactly one task per stage, and the assignment costs and interdiction impacts vary across stages. Before any stage commences in the game, the attacker can interdict arcs subject to a cardinality constraint. An interdicted arc can still be used by the user, but at an increased assignment cost. The goal is to find an optimal sequence of assignments, coupled with the attacker's optimal interdiction strategy. We prove that this problem is strongly NP-hard, even when the attacker can interdict only one arc. We propose an exact exponential-state dynamic-programming algorithm for this problem as well as lower and upper bounds on the optimal objective function value. Our bounds are based on classical interdiction and robust optimization models, and on variations of the DAI game. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 373-387, 2017 [ABSTRACT FROM AUTHOR]

In this paper, we present the existing literature on the human resource allocation problem. We study the main resolution approaches: exact, heuristic and metaheuristics methods proposed to solve the problem. We also examine the different studies from state-of the-art and classify them according to their real life applications in several areas such as production planning applications, maintenance management, hospital systems, project management, etc. Finally, we discuss and analyze the different contributions examined in this field. [ABSTRACT FROM AUTHOR]

The bipartite record linkage task consists of merging two disparate datafiles containing information on two overlapping sets of entities. This is nontrivial in the absence of unique identifiers and it is important for a wide variety of applications given that it needs to be solved whenever we have to combine information from different sources. Most statistical techniques currently used for record linkage are derived from a seminal article by Fellegi and Sunter in 1969. These techniques usually assume independence in the matching statuses of record pairs to derive estimation procedures and optimal point estimators. We argue that this independence assumption is unreasonable and instead target a bipartite matching between the two datafiles as our parameter of interest. Bayesian implementations allow us to quantify uncertainty on the matching decisions and derive a variety of point estimators using different loss functions. We propose partial Bayes estimates that allow uncertain parts of the bipartite matching to be left unresolved. We evaluate our approach to record linkage using a variety of challenging scenarios and show that it outperforms the traditional methodology. We illustrate the advantages of our methods merging two datafiles on casualties from the civil war of El Salvador. Supplementary materials for this article are available online. [ABSTRACT FROM AUTHOR]

One of the basic combinatorial optimization problems is the assignment problem that deals with the assigning of jobs to individuals. In traditional assignment problems, n jobs usually are assigned to n individuals such that the total cost is minimized or the total profit is maximized. However, in numerous real-life applications, various attributes could be considered in assignment problems while data (objective function coefficients) may be uncertain. Therefore, in the current paper, interval factors are taken in assignment problems where multiple attributes, inputs and outputs, are present. Indeed, an approach based on Data Envelopment Analysis (DEA) is proposed to solve the interval assignment problem with multiple attributes. To illustrate, the non-parametric technique (DEA) is utilized to specify the lower and upper bounds of the best final efficiency scores of an assignment plan. Also, the method suggested herein is illustrated and clarified by an application. [ABSTRACT FROM AUTHOR]

Least-Significant-Bit (LSB) is one of the popular and frequently used steganography techniques to hide a secret message in a digital medium. Its popularity is due to its simplicity in implementation and ease of use. However, such simplicity comes with vulnerabilities. An embedded secret message using the traditional LSB insertion is easily decodable when the stego image is suspected to be hiding a secret message. In this paper, we propose a novel secure and high quality LSB embedding technique. The security of the embedded payload is employed through introducing a novel quadratic embedding sequence. The embedding technique is also text dependent and has non-bounded inputs, making the possibilities of decoding infinite. Due to the exponential growth of and quadratic embedding, a novel cyclic technique is also introduced for the sequence that goes beyond the limits of the cover medium. The proposed method also aims to reduce the noise arising from embedding the secret message by reducing bits changed. This is done by partitioning the cover medium and the secret message into N partitions and artificially creating an assignment problem based on bit change criteria. The assignment problem will be solved using the Hungarian algorithm that will puzzle the secret message partition for an overall least bit change. [ABSTRACT FROM AUTHOR]

The assignment problem is an archetypal combinatorial optimization problem. This paper presents a neural network based on a dynamic model for solving the assignment problem. The main idea is to replace the assignment problem with a linear programming problem. On the basis of the Karush- Kuhn-Tucker optimality conditions, the equilibrium point of the proposed neural network is proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the assignment problem. Block diagram of the proposed model is given. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper. [ABSTRACT FROM AUTHOR]

We develop an integer programming model and an exact solution methodology for assigning aircrew members to training sessions which they need to attend in order to fulfill the requirements for renewal of their flight capability. The aim is to find the optimal assignment that minimizes the number of unassigned trainees, while also satisfying a variety of seniority, preference, capacity and language compatibility restrictions. The proposed methodology partitions the aircrew members into distinct groups based on their seniority, making the optimal assignment decisions pertaining to each of these groups sequentially. We present extensive computational results demonstrating that the proposed methodology enables the solution of realistic size problems in moderate computational times. [ABSTRACT FROM AUTHOR]

We present a consensus method which, given the two correspondences between sets of elements generated by separate entities, enounces a final correspondence consensus considering the existence of outliers . Our method is based on an optimisation technique that minimises the cost of the correspondence while forcing (to the most) to be the mean correspondence of the two original correspondences. The method decides the mapping of the elements that the original correspondences disagree and returns the same element mapping when both correspondences agree. We first show the validity of the method through an experiment in ideal conditions based on palmprint identification, and subsequently present two practical experiments based on image retrieval. [ABSTRACT FROM AUTHOR]

The moist available potential energy (MAPE) of a domain of air is defined as the maximum amount of kinetic energy that can be released through reversible adiabatic motions of its air parcels. The MAPE can be calculated using a parcel-moving algorithm that finds the minimum enthalpy state for a given set of thermodynamic assumptions. However, the parcel-moving algorithms proposed previously do not always find the minimum enthalpy state. In this article, we apply the Munkres algorithm to find the exact minimum enthalpy state and compare this exact algorithm with four inexact algorithms, including a new divide-and-conquer algorithm. The divide-and-conquer algorithm performs well in practice, while being simpler and faster than the Munkres algorithm, and it is recommended for future calculation of MAPE when the exact result is not required. [ABSTRACT FROM AUTHOR]

The passenger traffic is the most sensitive field in terms of the passengerś perception of the transport line layout. Every drawback will show soon and be transferred into the whole range of the provided services. The aim in the passenger traffic is to remove any obstacles that prevent the passengers from obtaining the continuous, available and high quality transport and to develop such activities to meet the requirements of the passengers as much as possible. [ABSTRACT FROM AUTHOR]

This article develops and implements time-dependent shortest path and assignment algorithms for vehicle routing and assignment during a no-notice evacuation. A time-dependent shortest path algorithm with arc labeling is designed to improve computer storage space efficiency. Visual Basic for Application (VBA) is used to improve time efficiency of both shortest path and assignment algorithms. Performance of the algorithms is analyzed and compared through implementation in VBA and the General Algebraic Modeling System (GAMS). Since VBA seamlessly integrates with Microsoft Excel and enables efficient data manipulation, the algorithms implemented in VBA are more efficient and obtain optimal solutions faster than those implemented in the GAMS. The shortest path algorithm with arc labeling implemented in VBA may be used for real-time vehicle routing for large road networks during no-notice evacuations. [ABSTRACT FROM AUTHOR]

This paper investigates how to assign individuals to suitable positions effectively and fairly. Firstly, some related standard mathematical evaluation methods such as DEA, total ranking method based on DEA and consensus formation method are reviewed. Secondly, using these methods and combining them under multi-criteria and scenarios, in Ishii (2014) we proposed two allocation models to assign suitable individuals to suitable positions, i.e., a ranking data model with respect to each position and a scenario model. Modifying a previous paper and the relative distance method by Cook and Kress (1984), a new consensus method is then proposed and applied to these two models. These models are firstly transformed into a transportation problem with a special structure since our model assumes that the number of positions does not exceed that of individuals, that is, it includes the case in which the number of positions is insufficient to cover all individuals. The transportation problem is then transformed into the classic assignment problem. From an optimal solution of the assignment problem, an optimal allocation of individuals to positions is found for each model. Finally the paper concludes by showing the results and discussing applicability of the model to other allocation problems and to other evaluation methods that use linguistic terms denoting the suitability of individuals to positions. [ABSTRACT FROM AUTHOR]

In this paper, we examine the freight scheduling problem and the design of decision support systems in rail transport. We present an intelligent control system that solves the engine and crew scheduling problem. The problem of freight scheduling is modelled as an assignment and optimization problem and solved using two different algorithms: the method of auctions and the simulated annealing method. The algorithms were adopted in order to optimize the solution while accounting for domain-specific features of rail transportation technology. A comparative evaluation of the two approaches allowed us to design a hybrid combined method which we apply in the development of an intelligent transport control system for scheduling rail traffic across the East Siberian Railway. [ABSTRACT FROM AUTHOR]

With the popularity of mobile computing and social media, various kinds of online event-based social network (EBSN) platforms, such as Meetup, Plancast and Whova, are gaining in prominence. A fundamental task of managing EBSN platforms is to recommend suitable social events to potential users according to the following three factors: spatial locations of events and users, attribute similarities between events and users, and friend relationships among users. However, none of the existing approaches considers all the aforementioned influential factors when they recommend users to proper events. Furthermore, the existing recommendation strategies neglect the bottleneck cases of the global recommendation. Thus, it is impossible for the existing recommendation solutions to be fair in real-world scenarios. In this paper, we first formally define the problem of bottleneck-aware social event arrangement (BSEA), which is proven to be NP-hard. To solve the BSEA problem approximately, we devise two greedy heuristic algorithms, Greedy and Random+Greedy, and a local-search-based optimization technique. In particular, the Greedy algorithm is more effective but less efficient than the Random+Greedy algorithm in most cases. Moreover, a variant of the BSEA problem, called the Extended BSEA problem, is studied, and the above solutions can be extended to address this variant easily. Finally, we conduct extensive experiments on real and synthetic datasets which verify the efficiency and effectiveness of our proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper we study the d -dimensional assignment problem in which entries of the cost array satisfy the Monge property, except for ∞ -entries, which may violate it. We assume that the ∞ -entries are incurred by incompatible partner indices and their number is bounded by an upper bound λ for each index. We show that the problem can be solved in linear time for fixed d and λ , and it becomes strongly NP-hard if d or λ is part of the input. [ABSTRACT FROM AUTHOR]

Factors contributing to winning games are imperative, as the ultimate objective in a game is victory. The aim of this study was to identify the factors that characterize the game of cricket, and to investigate the factors that truly influence the result of a game using the data collected from the Champions Trophy cricket tournament. According to the results, this cricket tournament can be characterized using the factors of batting, bowling, and decision-making. Further investigation suggests that the rank of the team and the number of runs they score have the most significant influence on the result of games. As far as the effectiveness of assigning bowlers is concerned, the Australian team has done a fabulous job compared to the rest of the teams. [ABSTRACT FROM AUTHOR]

A bus station contains several bus stops. Only one bus can occupy a singlebus stop at a time. Buses of many trips arrive to the bus station during the day (or duringanother considered period) and every bus occupies a bus stop for a certain time interval.The set of available bus stops is limited. This paper studies a problem how to assign a busstop to every bus trip in order to minimize the number of assigned bus stops and in orderto comply several additional conditions. Several approaches to this problem arepresented. These approaches differ according to considered additional conditions.

Matching is a part of graph theory that discuss to make a pair, that can be used to solve many problems; one of them is the assignment problem. The assignment problem is to make a pair problem for n as the employees and for n as the duties, therefore each employee gets one duty, and each duty is given exactly for each employee. The assignment problem can be solved by determining the matching in weighted bipartite graph through Hungarian Method. It can be determined from the alternating tree of a formed edge. If there is augmenting path, that augmenting path is used to form the more number of matching. If the formed path is alternating path, therefore the process is labeling the new node until finding the augmenting vertices. This matching is called as the perfect matching with the number of maximum weighed side in weighted bipartite graphs. The result matching is the solution for the assignment problem by giving an employee with a duty.