Search

Critical chain buffer management (CCBM) has been extensively studied in recent years. This paper investigates a new formulation of CCBM, the multimode chance-constrained CCBM problem. A flow-based mixed-integer linear programming model is described and the chance constraints are tackled using a scenario approach. A reinforcement learning (RL)-based algorithm is proposed to solve the problem. A factorial experiment is conducted and the results of this study indicate that solving the chance-constrained problem produces shorter project durations than the traditional approach that inserts time buffers into a baseline schedule generated by solving the deterministic problem. This paper also demonstrates that our RL method produces competitive schedules compared to established benchmarks. The importance of solving the chance-constrained problem and obtaining a project buffer tailored to the desired probability of completing the project on schedule directly from the solution is highlighted. Because of its potential for generating shorter schedules with the same on-time probabilities as the traditional approach, this research can be a useful aid for decision makers. [ABSTRACT FROM AUTHOR]

Businesses nowadays often feel impelled to rush and implement Big Data and Artificial Intelligence initiatives in their organizations without clarity on their business problems, nor the appropriate methodologies for extracting actionable insights from the data. In contrast, this paper presents a process that starts with an articulated business problem instead of a "data rush". The presented process, dubbed the Business-Driven Data-Supported (BDDS) process, is rigorously anchored in concepts from Theory of Constraints and Information Theory. BDDS guides businesses in solving their problems by stating observed performance gaps, uncovering their underlying root cause, formulating the "right question", utilizing only the "right data", and choosing the "right methodology" to extract the "right information" from the data, leading to the "right actionable insights." Also provided is a prescriptive framework, dubbed the Data-to-Information-Extraction-Methodology (DIEM), for selecting the "right methodology", based on the understanding level of relevant system dependencies and the availability of relevant data. The BDDS process is illustrated by an example from the healthcare industry, and the efficacy and applicability of the DIEM framework are supported by eleven case studies from a broad range of industries. [ABSTRACT FROM AUTHOR]

In this paper, an optimal maintenance policy is developed for a k-out-of-n system that works in a random cycle. A k-out-of-n system, which consists of n independent components and functions if at least k of the n components function, is one of the most important systems in reliability engineering. Consider that a component suffers from either minor or catastrophic failure, which is minimally repaired or lying idle, respectively. When n - k + 1 idle components occur, the system completely fails and undergoes corrective replacement. The notations of preventive replacement first and last are adopted; in other words, the system undergoes preventive replacement before complete failure at a planned time or at a random working time, whichever occurs first or last. The present paper aims to develop a two-stage maintenance methodology for a k-out-of-n system, and determine the optimal number of components and preventive replacement time that minimize the mean cost rate functions, respectively. For each model, the mean cost rate function is formulated analytically and the optimization problem is solved theoretically. Finally, a numerical example is given to demonstrate the applicability of the methodology derived from this paper. The proposed models provide a more general framework to analyze the maintenance policy for the k-out-of-n system. [ABSTRACT FROM AUTHOR]

As is well-known, transition probabilities of jump Markov processes satisfy Kolmogorov's backward and forward equations. In the seminal 1940 paper, William Feller investigated solutions of Kolmogorov's equations for jump Markov processes. Recently the authors solved the problem studied by Feller and showed that the minimal solution of Kolmogorov's backward and forward equations is the transition probability of the corresponding jump Markov process if the transition rate at each state is bounded. This paper presents more general results. For Kolmogorov's backward equation, the sufficient condition for the described property of the minimal solution is that the transition rate at each state is locally integrable, and for Kolmogorov's forward equation the corresponding sufficient condition is that the transition rate at each state is locally bounded. [ABSTRACT FROM AUTHOR]

Analytical Hierarchy Process (AHP) has evolved since its inception and has contributed mainly to multi-criteria decision-making (MCDM) to solve complex problems. It is a widespread technique that uses group decision-making approach to solve problems in business operations, mathematics, and numerous other scientific fields. While its applications are numerous, a handful of researchers have studied the growth trajectory of AHP. Whilst these seminal works have discussed the evolution of AHP in different contexts and using contemporary techniques, we complement them by presenting and reflecting on the unchartered and pressing need of charting the managerial and theoretical evolution of AHP, over the last decade. We do this through a systematic and thematic review of the extant literature. This study uses the Scopus database to extract papers published between 2012 and 2021 in decision science with an overlap with operations research and information systems. The study follows Tranfield et al. (2003)'s guidelines to understand the past trends of AHP along three key dimensions and offers future directions. The study also showcases key trends using historiography and uses data visualization techniques to understand the use of AHP with other MCDM techniques. [ABSTRACT FROM AUTHOR]

During the transmission of several different commodities from respective sources to the sinks, there may be loss due to leakage, evaporation, or damage. The generalized multi-commodity flow problem on a lossy network deals with the transshipment of these commodities from the origin nodes to the destination nodes − not violating the capacity constraints on each arc with minimum loss. Partial lane reversal strategy makes traffic systematic and smooth by flipping the orientation of necessary road segments that improve the flow value and significantly minimize the loss. In this paper, we introduce maximum generalized static multi-commodity flow, maximum generalized dynamic multi-commodity flow, and generalized earliest arrival multi-commodity flow problems on a lossy network with partial lane reversals, and present algorithms to solve these problems in pseudo-polynomial time complexity. We also present a fully polynomial-time approximation scheme for the maximum generalized dynamic multi-commodity flow problem with partial lane reversals. [ABSTRACT FROM AUTHOR]

One of the key issues in transportation systems is allocating shipping orders to the most appropriate drivers in the shortest time and with the maximum profit. Many studies were carried out in the transportation service procurement process for allocating orders, but none of them considered driver-to-driver interactions and applied information diffusion concepts as a framework to maximize the profit, due to the lack of a framework to model the interactions. In this paper, we present a weighted drivers' collaboration network to form the interactions. To predict the behavior of drivers, a new community detection algorithm is developed to extract communities and their leaders in terms of the speed and power of receiving and diffusing shipping orders. In addition, we present a profit maximization model that utilizes the information diffusion power of community leaders. The results show the model is able to allocate shipping orders to the most suitable drivers in the shortest possible time and with the highest profit. To demonstrate the performance of the developed algorithm, we present a numerical example. Finally, a case study is applied to solve the optimization problem. The results show that the optimized behavior of companies in allocating orders to drivers is based on their risk level, reputation, and the average number of their customers. [ABSTRACT FROM AUTHOR]

In this paper, we consider an abstract regularized method with a skew-symmetric mapping as regularization for solving equilibrium problems. The regularized equilibrium problem can be viewed as a generalized mixed equilibrium problem and some existence and uniqueness results are analyzed in order to study the convergence properties of the algorithm. The proposed method retrieves some existing one in the literature on equilibrium problems. We provide some numerical tests to illustrate the performance of the method. We also propose an original application to Becker's household behavior theory using the variational rationality approach of human dynamics. [ABSTRACT FROM AUTHOR]

This paper considers an integrated approach to two common problems in a precision agriculture framework: management zone delineation and selective harvest scheduling. Our model minimizes the total costs of harvest operations, establishing planning and scheduling for selective harvest of each selected management zone. Therefore, this tool provides important information for decision making of farmers in the field. Our integrated model is contrasted with the hierarchical approach commonly used in the literature for these cases, where the result of zoning problem is an input to schedule the harvest problem. Both problems were solved through a complete enumeration of all the potential management zones and demonstrated the advantages of our proposed model over the hierarchical approach. Our model reached an average reduction of 10% in harvest operations costs for different instances in a case study. [ABSTRACT FROM AUTHOR]

The paper tackles a class of bilevel programming where the upper level problem and the lower level problem are integer indefinite quadratic programs. This article presents a new algorithm for solving the integer indefinite quadratic bilevel problem, say IIQBP. Indeed, the upper level indefinite quadratic problem is solved, the optimal solution of which belongs to the efficient solutions set of the corresponding bicriteria problem. The set of efficient solutions is determined by branch and bound method with cuts. The found integer optimal solution is tested for optimality of the main problem by solving the lower level problem. If this solution is non optimal of IIQBP problem, a cut is added to the upper level problem and a new efficient solutions set is determined then a new integer solution of the upper level problem is found. After the presentation and validation of the algorithm, two examples are provided to better visualize the proposed algorithm. [ABSTRACT FROM AUTHOR]

Though interfirm collaboration on carbon emission reduction, the cross-enterprise flow of emission reduction resources and improved efficiency in greenhouse gas reduction can be realized. Especially in the context of big data, enterprises can find suitable partners for emission reduction faster and more accurately through interfirm collaboration. However, similar to other cooperative modes, revenue allocation is the key to ensuring the stability of the collaborative emission reduction system. Based on the premise of carbon trading, this paper discusses revenue allocation among enterprises participating in the collaborative emission reduction process under complete information in a big data context. Specifically, we constructed a Shapley value analysis model of revenue allocation for interfirm collaboration on carbon emission reduction, and amended this model with investment cost and risk-bearing. Consequently, this research provides not only a theoretical basis for solving the problem of revenue distribution in the process of collaborative emission reductions among enterprises but also a theoretical guide for enterprises countermeasures following the completion of China's future carbon trading mechanism. [ABSTRACT FROM AUTHOR]

In this research, an agro-supply chain in the context of both economic and environmental issues has been investigated. To this end, a bi-objective model is formulated as a mixed-integer linear programming that aims to minimize the total costs and CO2 emissions. It generates the integration between purchasing, transporting, and storing decisions, considering specific characteristics of agro-products such as seasonality, perishability, and uncertainty. This study provides a different set of temperature conditions for preserving products from spoilage. In addition, a robust optimization approach is used to tackle the uncertainty in this paper. Then, ε -constraint method is used to convert the bi-objective model to a single one. To solve the problem, Lagrangian relaxation algorithm is applied as an efficient approach giving lower bounds for the original problem and used for estimating upper bounds. At the end, a real case study is presented to give valuable insight via assessing the impacts of uncertainty in system costs. [ABSTRACT FROM AUTHOR]

This paper concerns a disassembly line balancing problem (DLBP) in remanufacturing that aims to allocate a set of tasks to workstations to disassemble a product. We consider two objectives in the same time, i.e., minimising the number of workstations required and minimising the operating costs. A common approach to such problems is to covert the multiple objectives into a single one and solve the resulting problem with either exact or heuristic methods. However, the appropriate weights must be determined a priori, yet the results provide little insight on the trade-off between competing objectives. Moreover, DLBP problems are proven NP-complete and thus the solvable instances by exact methods are limited. To this end, we formulate the problem into a multi-objective dynamic program and prove the monotonicity property of both objective functions. A backward recursive algorithm is developed to efficiently generate all the non-dominated solutions. The numerical results show that our proposal is more efficient than alternative exact algorithms proposed in the literature and can handle much larger problem instances. [ABSTRACT FROM AUTHOR]

We consider a stochastic discrete multiobjective programming process with a finite number of stages. The number of states at each stage and the number of feasible decisions at each state are also finite. The aim of the paper is to propose a new interactive procedure for such a problem based on trade-off analysis. The procedure is illustrated with project portfolio selection. There are many organizations with moderately large portfolios of projects. Although the problem under discussion is not very large, it is difficult to solve, since projects are not implemented simultaneously. Moreover, the companies must take into account the risk that a particular project, which is planned to start in the future, may not be ready for implementation. We present an interactive trade-off procedure, based on the stochastic approach, as a new proposition to solve such a problem. [ABSTRACT FROM AUTHOR]

In this paper, we extend the previous method for solving inverse problems for steady-state equations using the Generalized Collage Theorem by searching for an approximation that not only minimizes the collage error but also maximizes the entropy and minimizes the sparsity. In this extended formulation, the parameter estimation minimization problem can be understood as a multiple criteria problem, with three different and conflicting criteria: The generalized collage error, the entropy associated with the unknown parameters, and the sparsity of the set of unknown parameters. We implement a scalarization technique to reduce the multiple criteria program to a single criterion one, by combining all objective functions with different trade-off weights. Numerical examples confirm that the collage method produces good, but sub-optimal, results. A relatively low-weighted entropy term allows for better approximations while the sparsity term decreases the complexity of the solution in terms of the number of elements in the basis. [ABSTRACT FROM AUTHOR]

Network reliability is famous for its problem solving ability in several real-life applications. However, due to its NP-hard nature (Ball in IEEE Trans Reliab 35(3):230–238, 1986), researchers are devoted to the improvement of computational efficiency in various approaches. Although flow in networks depicts its combination properties, only few of them are useful in the calculation of network reliability. In some point of views, we call it mining in flow data. This paper presents techniques of how to efficiently do the flow data mining tasks. A skill based on backtrack and maximal flow is illustrated with examples and benchmarks. The results show that the proposed approach is valuable in the calculation of network reliability. [ABSTRACT FROM AUTHOR]

This paper introduces an interactive framework to guide decision-makers in a multi-criteria supplier selection process. State-of-the-art multi-criteria methods for supplier selection elicit the decision-maker's preferences among the criteria by processing pre-collected data from different stakeholders. We propose a different approach where the preferences are elicited through an active learning loop. At each step, the framework optimally solves a combinatorial problem multiple times with different weights assigned to the objectives. Afterwards, a pair of solutions among those computed is selected using a particular query selection strategy, and the decision-maker expresses a preference between them. These two steps are repeated until a specific stopping criterion is satisfied. We also introduce two novel fast query selection strategies, and we compare them with a myopically optimal query selection strategy. Computational experiments on a large set of randomly generated instances are used to examine the performance of our query selection strategies, showing a better computation time and similar performance in terms of the number of queries taken to achieve convergence. Our experimental results also show the usability of the framework for real-world problems with respect to the execution time and the number of loops needed to achieve convergence. [ABSTRACT FROM AUTHOR]

In this paper, we extend techniques developed in the context of the Travelling Salesperson Problem for cycle problems. Particularly, we study the shrinking of support graphs and the exact algorithms for subcycle elimination separation problems. The efficient application of the considered techniques has proved to be essential in the Travelling Salesperson Problem when solving large size problems by Branch-and-Cut, and this has been the motivation behind this work. Regarding the shrinking of support graphs, we prove the validity of the Padberg–Rinaldi general shrinking rules and the Crowder–Padberg subcycle-safe shrinking rules. Concerning the subcycle separation problems, we extend two exact separation algorithms, the Dynamic Hong and the Extended Padberg–Grötschel algorithms, which are shown to be superior to the ones used so far in the literature of cycle problems. The proposed techniques are empirically tested in 24 subcycle elimination problem instances generated by solving the Orienteering Problem (involving up to 15,112 vertices) with Branch-and-Cut. The experiments suggest the relevance of the proposed techniques for cycle problems. The obtained average speedup for the subcycle separation problems in the Orienteering Problem when the proposed techniques are used together is around 50 times in medium-sized instances and around 250 times in large-sized instances. [ABSTRACT FROM AUTHOR]

This paper presents an integer programming model and a matheuristic for the physician rostering problem. Constraints related to physician's preferences, legal restrictions, hospital requirements and workload balance are investigated. Moreover, a comparison of physician and nurse rostering is analyzed to identify common constraints present in both problems. The lack of a mathematical model that could be applied in the studied problem motivated the development of a new formulation. Data and constraints of the proposed physician rostering problem were provided by Hospital de Clínicas de Porto Alegre (HCPA), Brazil. Due to the difficulty of solving large instances, a matheuristic which combines integer programming and heuristic techniques was proposed to approach the problem. Computational experiments were conducted employing commercial and open-source solvers. Results revealed that open-source solvers are a good alternative to solve small problems, while the proposed matheuristic generated near-optimal results within acceptable computation time employing larger instances. [ABSTRACT FROM AUTHOR]

This paper is concerned with the computation of equilibrium for an exchange economy with constant returns production technologies. We convert such an economy into a pure exchange economy by allocating the production to each consumer's endowment evenly. In this way, the market clearing condition of the original economy is reformulated as that of a pure exchange economy, together with an additional complementarity condition to ensure the feasibility of production plans. A homotopy method is proposed to solve these two problems simultaneously. With this approach, the economic equilibrium model with constant returns production can be handled in a similar way to the pure exchange economy. A path-following algorithm is then developed for computing equilibria in these economies. [ABSTRACT FROM AUTHOR]

The aim of this paper is to determine the optimal balance between extraction and storage of a natural resource (in particular crude oil) over time under a large array of environmental, operational and financial constraints for an infinite maturity time. We consider a manager that owns an oil field from which he can extract oil and decides to sell or store it. This operational strategy has to be carried out in continuous time and has to satisfy physical, operational, environmental and financial constraints such as storage capacity, crude oil spot price volatility, amount available for possible extraction or maximum amount that could be invested at time t for the extraction choice. The costs of storage and extraction are also taken into account to better fit the real market scenario. We solve the optimization problem of the manager's profit under this large array of constraints and provide an optimal strategy. We then examine different numerical scenarios to check the robustness and the corresponding optimal strategies given by our model, which is obtained by a numerical approach, with respect to different possible events related to the market, environmental policies or ecological constraints. [ABSTRACT FROM AUTHOR]

In recent years, reasoning under uncertainty in multi-objective problems has become an active research area. However, solving this kind of problems reveals many performance and robustness issues that have been so far been neglected. Most of existing studies in this area are focused on dealing with robustness in the field of mono-objective optimization. The aim of the present paper is to address robustness of multi-objective optimization problems over uncertain inputs data. In particular, we focus on the specific case of fuzziness propagation to the multiple objectives in such problems. Then in order to avoid the loss of efficiency of fuzzy-valued objective values, we introduce new robustness techniques combining fuzziness and multi-objective context. [ABSTRACT FROM AUTHOR]

This paper proposes a multi-start randomized heuristic for solving real-life crew rostering problems in airlines. The paper describes realistic constrains, regulations, and rules that have not been considered in the literature so far. Our algorithm is designed to provide quality solutions satisfying these real-life specifications while, at the same time, it aims at balancing the workload distribution among the different crewmembers. Thus, our approach promotes corporate social responsibility by distributing the workload in a fair way and avoiding that some crewmembers get unnecessarily overstressed. Despite its importance in real-life applications, these aspects have seldom been considered in the crew scheduling literature, where most solving approaches refer to simplified models and are tested on non-realistic benchmarks. The experimental tests show that our algorithm is capable of generating feasible quality solutions to real-life crew rostering problems in just a few seconds. These times are orders of magnitude lower than the times currently employed by some airlines to obtain a single feasible solution, since the 'optimal' solutions provided by most commercial software usually require additional adjustments in order to meet all the real-life specifications. [ABSTRACT FROM AUTHOR]

In this paper, we consider capacity expansion for network models subject to uncertainty and budget constraints. We use a scenario tree approach to handle the uncertainty and construct a multi-stage stochastic mixed-integer programming model for the network capacity expansion problem. We assume that permanent capacity and spot market capacity are available, which can be used permanently or temporarily by the decision maker respectively. By relaxing the budget constraints, we propose a heuristic Lagrangian relaxation method to solve the problem. Two algorithms are developed to find tight upper bounds for the Lagrangian relaxation procedure. The experimental results show superior performance of the proposed Lagrangian relaxation method compared with CPLEX. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of improving an existing road network in the context of strategic planning through the creation of new highway corridors. To address this problem we analyse three mixed integer programming models. The so-called [P1] is the classical capacitated multicommodity network design model. The model named [P2] imposes on [P1] the location of a single (main path) highway corridor in the road network and [P3] adds to [P2] a set of sub-tour breaking constraints. The stated goal is to minimize the total travel time for a known origin-destination demand matrix with a given budget. In this paper we propose an efficient method for [P3], based on a Lagrangian relaxation, to obtain easily-solved sub-problems. A cutting-plane method for solving the Lagrangian sub-problems is proposed. This method generates valid cuts until an optimal solution is found. The Lagrangian dual problem is solved using the sub-gradient optimization method. A case study has been carried out for the region of Castilla-La Mancha (Spain). Computational comparisons between the proposed method and a state-of-the-art mixed-integer code are presented. The Lagrangian relaxation approach is found to be capable of generating good feasible solutions to the case study within a reasonable computational time. [ABSTRACT FROM AUTHOR]

The paper presents new approximability results for single machine scheduling problems with jobs requiring some non-renewable resources (like raw materials, energy, or money) beside the machine. Each resource has an initial stock and additional supplies over time. A feasible schedule specifies a starting time for each job such that no two jobs overlap in time, and when a job is started, enough resources are available to cover its requirements. The goal is to find a feasible schedule of minimum makespan. This problem is strongly NP-hard. Recently, the authors of this paper have proposed a PTAS for the special case with a single non-renewable resource and with a constant number of supply dates, as well as an FPTAS for the special case with two supply dates and one resource only. In this paper we prove APX-hardness of the problem when the number of resources is part of the input, and new polynomial time approximation schemes are devised for some variants, including (1) job release dates, and more than one, but constant number of resources and resource supply dates, and (2) only one resource, arbitrary number of supply dates and job release dates, but with resource requirements proportional to job processing times. [ABSTRACT FROM AUTHOR]

The examination timetabling problem (ETTP) consists in the assignment of specific dates to the exams of a set of courses assuming that the course enrollments are known. This problem is also known as post-enrollment ETTP. In this paper, we describe and solve a variant of the ETTP which has two particularities: (1) it does not assume the course enrollments as known and uses the curriculum of the degree program to evaluate potential conflicts in the exam schedules, and (2) it considers the exams and classrooms of multiple degree programs simultaneously. We refer to this variant of the ETTP as curriculum-based examination timetabling problem (CB-ETTP), a problem faced by many universities worldwide, being the Universidad Diego Portales (UDP) in Santiago of Chile one of them. To the best of our knowledge, this problem has not been described as such in the ETTP literature. We propose an approach to solve the CB-ETTP consisting of four sequential stages. The first stage groups courses into clusters and generates classroom configurations called room patterns. The second stage assigns time slots and room patterns to course clusters. Then, the third stage assigns time slots and room patterns to individual courses. Finally, the fourth stage generates a definitive exam schedule assigning specific rooms to each course exam. We evaluate the performance of the proposed approach by applying it to real-world instances generated based on data provided by the Faculty of Engineering at the UDP. The results show a reduction in the number of conflicts and rescheduling with respect to the current exam scheduling practice used by this university. [ABSTRACT FROM AUTHOR]

This paper considers the component assignment problem (CAP) of finding the optimal assignment of n available components to n positions in a system such that the system reliability is maximized. To solve the CAP, an important type of problems in reliability, we propose a Birnbaum-importance based genetic local search (BIGLS) algorithm in which a local search using the Birnbaum importance is embedded into the genetic algorithm. This paper presents comprehensive numerical tests to compare the performance of the BIGLS with a general genetic algorithm and a Birnbaum-importance based two-stage heuristic. The testing results show that the BIGLS is robust (with respect to its random operations) and effective, and outperforms two benchmark methods in terms of solution quality. It demonstrates the effectiveness of embedding the Birnbaum importance in the local search under the genetic evolutionary mechanism. [ABSTRACT FROM AUTHOR]

This paper deals with minimization of the variances of the total discounted costs for constrained Continuous-Time Markov Decision Processes (CTMDPs). The costs consist of cumulative costs incurred between jumps and instant costs incurred at jump epochs. We interpret discounting as an exponentially distributed stopping time. According to existing theory, for the expected total discounted costs optimal policies exist in the forms of randomized stationary and switching stationary policies. While the former is typically unique, the latter forms a finite set whose number of elements grows exponentially with the number of constraints. This paper investigates the problem when the process stops immediately after the first jump. For costs up to the first jump we provide an index for selection of actions by switching stationary policies and show that the indexed switching policy achieves a smaller variance than the randomized stationary policy. For problems without instant costs, the indexed switching policy achieves the minimum variance of costs up to the first jump among all the equivalent switching policies. [ABSTRACT FROM AUTHOR]

This paper proposes an adaptation, to the two-dimensional irregular bin packing problem of the Djang and Finch heuristic (DJD), originally designed for the one-dimensional bin packing problem. In the two-dimensional case, not only is it the case that the piece's size is important but its shape also has a significant influence. Therefore, DJD as a selection heuristic has to be paired with a placement heuristic to completely construct a solution to the underlying packing problem. A successful adaptation of the DJD requires a routine to reduce computational costs, which is also proposed and successfully tested in this paper. Results, on a wide variety of instance types with convex polygons, are found to be significantly better than those produced by more conventional selection heuristics. [ABSTRACT FROM AUTHOR]

This paper considers the capacitated multi-level lot-sizing problem with setup times, a class of difficult problems often faced in practical production planning settings. In the literature, relax-and-fix is a technique commonly applied to solve this problem due to the fact that setup decisions in later periods of the planning horizon are sensitive to setup decisions in the early periods but not vice versa. However, the weakness of this method is that setup decisions are optimized only on a small subset of periods in each iteration, and setup decisions fixed in early iterations might adversely affect setup decisions in later periods. In order to avoid these weaknesses, this paper proposes an extended relax-and-fix based heuristic that systematically uses domain knowledge derived from several strategies of relax-and-fix and a linear programming relaxation technique. Computational results show that the proposed heuristic is superior to other well-known approaches on solution qualities, in particular on hard test instances. [ABSTRACT FROM AUTHOR]

The organization of a specialized transportation system to perform transports for elderly and handicapped people is usually modeled as dial-a-ride problem. Users place transportation requests with specified pickup and delivery locations and times. The requests have to be completed under user inconvenience considerations by a specified fleet of vehicles. In the dial-a-ride problem, the aim is to minimize the total travel times respecting the given time windows, the maximum user ride times, and the vehicle restrictions. This paper introduces a dynamic programming algorithm for the dial-a-ride problem and demonstrates its effective application in (hybrid) metaheuristic approaches. Compared to most of the works presented in literature, this approach does not make use of any (commercial) solver. We present an exact dynamic programming algorithm and a dynamic programming based metaheuristic, which restricts the considered solution space. Then, we propose a hybrid metaheuristic algorithm which integrates the dynamic programming based algorithms into a large neighborhood framework. The algorithms are tested on a given set of benchmark instances from the literature and compared to a state-of-the-art hybrid large neighborhood search approach. [ABSTRACT FROM AUTHOR]

In this paper we present a greedy algorithm for solving the problem of the maximum partitioning of graphs with supply and demand (MPGSD). The goal of the method is to solve the MPGSD for large graphs in a reasonable time limit. This is done by using a two stage greedy algorithm, with two corresponding types of heuristics. The solutions acquired in this way are improved by applying a computationally inexpensive, hill climbing like, greedy correction procedure. In our numeric experiments we analyze different heuristic functions for each stage of the greedy algorithm, and show that their performance is highly dependent on the properties of the specific instance. Our tests show that by exploring a relatively small number of solutions generated by combining different heuristic functions, and applying the proposed correction procedure we can find solutions within only a few percent of the optimal ones. [ABSTRACT FROM AUTHOR]

In this paper potential usage of different correlation measures in portfolio problems is studied. We characterize especially semidefinite positive correlation measures consistent with the choices of risk-averse investors. Moreover, we propose a new approach to portfolio selection problem, which optimizes the correlation between the portfolio and one or two market benchmarks. We also discuss why should correlation measures be used to reduce the dimensionality of large scale portfolio problems. Finally, through an empirical analysis, we show the impact of different correlation measures on portfolio selection problems and on dimensionality reduction problems. In particular, we compare the ex post sample paths of several portfolio strategies based on different risk measures and correlation measures. [ABSTRACT FROM AUTHOR]

In a typical project portfolio optimization problem, the decision makers would choose the optimal project portfolio from the candidates under the constraints of certain resources. However, in lots of real world examples, traditional approaches cannot perfectly solve the project portfolio optimization problems with unknown information about the importance of attributes. An innovative feature of this paper is to propose a stochastic multiattribute acceptability analysis (SMAA) to solve the multiattribute project portfolio optimization problems. SMAA includes a series of methods, which provide full ranks for a set of alternatives by exploring the weight space to make each alternative the most preferred one. Our proposed method provides feasible procedures to deal with the project portfolio optimization problems and, as an extension of traditional SMAA methods, expands the SMAA applications from the comparison of single alternatives to the comparison of sets of alternatives. [ABSTRACT FROM AUTHOR]

The common fixed cost or revenue distribution amongst decision making units (briefly, DMUs) in an equitable way is one of the problems that can be solved by data envelopment analysis (DEA) concept. The motivation of this paper is common fixed cost or revenue allocation based on following three principles: First, allocation must be directly proportional to the elements (inputs and outputs) that are directly proportional to imposed common fixed cost or to obtained common fixed revenue. Second, allocation must be inversely proportional to the elements that are inversely proportional to common fixed cost or revenue. Finally, the elements that have no effect on common fixed cost or revenue must have no effect on allocation as well. [ABSTRACT FROM AUTHOR]

In this paper, we consider the optimal investment and optimal reinsurance problems for an insurer under the criterion of mean-variance with bankruptcy prohibition, i.e., the wealth process of the insurer is not allowed to be below zero at any time. The risk process is a diffusion model and the insurer can invest in a risk-free asset and multiple risky assets. In view of the standard martingale approach in tackling continuous-time portfolio choice models, we consider two subproblems. After solving the two subproblems respectively, we can obtain the solution to the mean-variance optimal problem. We also consider the optimal problem when bankruptcy is allowed. In this situation, we obtain the efficient strategy and efficient frontier using the stochastic linear-quadratic control theory. Then we compare the results in the two cases and give a numerical example to illustrate our results. [ABSTRACT FROM AUTHOR]

The importance measures have been a sensitivity analysis for a probabilistic system and are applied in diverse fields along with other design tools. This paper provides a comprehensive view on modeling the importance measures to solve the reliability problems such as component assignment problems, redundancy allocation, system upgrading, and fault diagnosis and maintenance. It also investigates importance measures in broad applications such as networks, mathematical programming, sensitivity and uncertainty analysis, and probabilistic risk analysis and probabilistic safety assessment. The importance-measure based methods are among the most practical decision tools. [ABSTRACT FROM AUTHOR]

In this paper we study lifetime properties of binary coherent systems from a state-level perspective. We define and study a system whose performance levels are determined by its total number of working components and structure. That is, the more working components the better performance level for the system. This enables us to make a more detailed analysis of a binary system. We obtain the distributions of the time that is spent by the system in a specific state subset and a specific state. Our analysis is based on the use of system signature. We also define an optimization problem concerned with the determination of the number of warm standby components. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of open shop scheduling on two machines with resources constraints. In the context of our study, in order to be executed, a job requires first, for its preparation for a given period of time, a number of resources which cannot exceed a given resource capacity. Then, it goes onto its execution while the resources allocated to it become available again. We seek a schedule that minimizes the makespan. We first prove the $\mathcal{N}\mathcal{P}$ -hardness of several versions of this problem. Then, we present a well solvable case, lower bounds, and heuristic algorithms along with an experimental study. [ABSTRACT FROM AUTHOR]

This paper presents a stochastic mixed integer programming model for a comprehensive hybrid power system design problem, including renewable energy generation, storage device, transmission network, and thermal generators, for remote areas. Given the complexity of the model, we developed a Benders' decomposition algorithm with two additional types of cutting planes: Pareto-optimal cuts generated using a modified Magnanti-Wong method and cuts generated from a maximum feasible subsystem. Computational results show significant improvement in our ability to solve this type of problem in comparison to a state-of-the-art professional solver. This model and the solution algorithm provide an analytical decision support tool for the hybrid power system design problem. [ABSTRACT FROM AUTHOR]

The optimal engineering design problem consists in minimizing the expected total cost of an infrastructure or equipment, including construction and expected repair costs, the latter depending on the failure probabilities of each failure mode. The solution becomes complex because the evaluation of failure probabilities using First-Order Reliability Methods (FORM) involves one optimization problem per failure mode. This paper formulates the optimal engineering design problem as a bi-level problem, i.e., an optimization problem constrained by a collection of other interrelated optimization problems. The structure of this bi-level problem is advantageously exploited using Benders' decomposition to develop and report an efficient algorithm to solve it. An advantage of the proposed approach is that the design optimization and the reliability calculations are decoupled, resulting in a structurally simple algorithm that exhibits high computational efficiency. Bi-level problems are non-convex by nature and Benders algorithm is intended for convex optimization. However, possible non-convexities can be detected and tackled using simple heuristics. Its practical interest is illustrated through a realistic but simple case study, a breakwater design example with two failure modes: overtopping and armor instability. [ABSTRACT FROM AUTHOR]

This paper shows how Benders decomposition can be used for estimating the parameters of a fatigue model. The objective function of such model depends on five parameters of different nature. This makes the parameter estimation problem of the fatigue model suitable for the Benders decomposition, which allows us to use well-behaved and robust parameter estimation methods for the different subproblems. To build the Benders cuts, explicit formulas for the sensitivities (partial derivatives) are obtained. This permits building the classical iterative method, in which upper and lower bounds of the optimal value of the objective function are obtained until convergence. Two alternative objective functions to be optimized are the likelihood and the sum of squares error functions, which relate to the maximum likelihood and the minimum error principles, respectively. The method is illustrated by its application to a real-world problem. [ABSTRACT FROM AUTHOR]

The airline's ability to offer flight schedules that provide service to passengers at desired times in competitive markets, while matching demand with an aircraft fleet of suitable size and composition, can significantly impact its profits. In this spirit, optional flight legs can be considered to construct a profitable schedule by optimally selecting among such alternatives in concert with assigning the available aircraft fleet to all the scheduled legs. Examining itinerary-based demands as well as multiple fare-classes can effectively capture network effects and realistic demand patterns. In addition, allowing flexibility on the departure times of scheduled flight legs can increase connection opportunities for passengers, hence yielding robust schedules while saving fleet assignment costs within the framework of an integrated model. Airlines can also capture an adequate market share by balancing flight schedules throughout the day, and recapture considerations can contribute to more realistic accepted demand realizations. We therefore propose in this paper a model that integrates the schedule design and fleet assignment processes while considering flexible flight times, schedule balance, and recapture issues, along with optional legs, path/itinerary-based demands, and multiple fare-classes. A polyhedral analysis is conducted to generate several classes of valid inequalities, which are used along with suitable separation routines to tighten the model representation. Solution approaches are designed by applying Benders decomposition method to the resulting tightened model, and computational results are presented using real data obtained from United Airlines to demonstrate the efficacy of the proposed procedures. [ABSTRACT FROM AUTHOR]

Presented in this paper is a self-contained analysis of a Markov decision problem that is known as the multi-armed bandit. The analysis covers the cases of linear and exponential utility functions. The optimal policy is shown to have a simple and easily-implemented form. Procedures for computing such a policy are presented, as are procedures for computing the expected utility that it earns, given any starting state. For the case of linear utility, constraints that link the bandits are introduced, and the constrained optimization problem is solved via column generation. The methodology is novel in several respects, which include the use of elementary row operations to simplify arguments. [ABSTRACT FROM AUTHOR]

In many appointment-based logistics systems customer orders may be served within a set of consecutive periods/days (i.e. a period window). In this case, the Multi-Period Vehicle Routing Problem (MPVRP) is relevant, and its efficient solution may lead to significant operational improvements. In this paper we investigate the MPVRP with Time Windows (MPVRPTW). The latter are time intervals within each period of the period window, during which service may be provided to the customer. A general model and an exact method to solve the MPVRPTW are presented. The solution method is based on column generation. Furthermore, two novel, efficient techniques to accelerate the solution procedure of the MPVRPTW are proposed. These techniques exploit the structure of the multi-period setting in order to identify similarities within the different subproblems and, thus, avoid solving every subproblem at each iteration. The experimental study analyzed the performance of the proposed methods systematically for various problem parameters, such as geographical distribution of customers and period window patterns. In most cases, the new methods improve significantly the efficiency of convergence to the optimal solution as compared to the classical method. [ABSTRACT FROM AUTHOR]

This paper characterizes and enumerates the possible solution structures in nonlinear pricing problem when the number of buyer types is given. It is shown that the single-crossing property, which is a standard assumption in the literature, reduces the complexity of solving the problem dramatically. The number of possible solution structures is important when the pricing problem is solved under limited information. [ABSTRACT FROM AUTHOR]

In this paper, we consider a parallel machine scheduling problem to minimize the total completion time. Each job belongs to a certain family. All jobs of one family have identical processing times. Major setups occur between jobs of different families, and we include sequence dependencies. Batches of jobs belonging to the same family can be formed to avoid these setups. Furthermore, we assume serial batching and batch availability. Therefore, the processing time of a batch is the sum of the processing times of all jobs grouped into the corresponding batch. An iterative method is developed for solving this specific problem. This approach alternates between varying batch sizes using an efficient heuristic and sequencing batches based on variable neighborhood search (VNS). Computational results demonstrate that the iterative heuristic outperforms heuristics based on a fixed batch size and list scheduling. [ABSTRACT FROM AUTHOR]

We consider an extension of the classic problem of division with claims to situations in which the characteristics of the agents are multi-dimensional. The proportional rule is the most prominent in the one-dimensional case, however there is no obvious way to define proportionality for the extended model. In this paper we introduce a property which generalizes proportionality, identify the family of rules satisfying it, and characterize a particular rule within this family on the basis of a property of symmetry. [ABSTRACT FROM AUTHOR]

A wireless sensor network (WSN) consists of a large number of unattended sensors with limited storage, battery power, computation, and communication capabilities, where battery power (or energy) is the most crucial resource for sensor nodes. The information sensed by sensors needs to be transmitted to sink quickly especially for the applications with delay restriction. However, it is difficult to achieve optimal energy efficiency and source-to-sink delay simultaneously. So it is very necessary to find a power control solution based tradeoff between energy and delay. In this paper, a cooperative differential game model is proposed, and a power solution is obtained which determines a fair distribution of the total cooperative cost among sources. [ABSTRACT FROM AUTHOR]