Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem an...
详细信息
Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.
The impact of imposing spatial wildlife constraints on long-range timber management schedules is examined for a public forest in northern Virginia under varying levels of a wildlife habitat constraint. Linear programm...
详细信息
The impact of imposing spatial wildlife constraints on long-range timber management schedules is examined for a public forest in northern Virginia under varying levels of a wildlife habitat constraint. Linear programming-based timber management scheduling models are solved using (1) standard linear programming, (2) mixed-integer programming with computer-determined stand allocations, and (3) mixed-integer programming with predetermined stand allocations in order to determine the extent to which the failure to consider explicitly the spatial aspects of a forest management problem with wildlife concerns may lead to an overestimation of timber production capacity. Findings indicate that present net value is overestimated by 1.8% to 21.4% and annual sawtimber harvest volume is overestimated by 2.6% to 13.5% when the standard linear programming approach is used.
The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in...
详细信息
The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable, We describe computational experience with a cutting plane algorithm for this problem.
In this paper we present an application of the scenario aggregation approach proposed by Rockafellar and Wets to a simple standard multi-product multi-period production planning problem with uncertain demand and setup...
详细信息
In this paper we present an application of the scenario aggregation approach proposed by Rockafellar and Wets to a simple standard multi-product multi-period production planning problem with uncertain demand and setup cost modelled by logical zero-one variables. The uncertainty in demand is expressed by a number of demand scenarios. As compared with more traditional approaches that require distributional assumptions and/or estimates of parameters from historical demand data, the scenario approach offers greater flexibility and makes it possible to take subjective information into account. The scenario aggregation principle and the corresponding progressive hedging algorithm offer a theoretically sound basis for generating consistent solutions for production planning models with uncertain demand. Since the production planning problem studied in this paper is of mixed-integer type the original scenario aggregation approach cannot be applied directly. However, since the integer variables in the production planning model are indirectly coupled to the continuous production decisions an alternative method in which only the production quantities are used to couple the different realizations can be used. This paper is a first attempt to perform this form of coupling. We illustrate the ideas on a small example and use this example to demonstrate how the solution can be evaluated in terms of flexibility measures.
Many optimization problems arising in practice are so complicated that the current tools for optimization do not supply a single, clean answer. We are forced to apply a variety of optimization methods on approximate m...
详细信息
Many optimization problems arising in practice are so complicated that the current tools for optimization do not supply a single, clean answer. We are forced to apply a variety of optimization methods on approximate models, so that we also obtain a variety of approximate solutions. Using a production-allocation problem in Philips Electronics Industries as a vehicle for communication, we generate several near-optimal solutions via decomposition, piece-wise linear programming, and mixed-integer programming. Next, we show that multi-criteria analysis could be used to select one of the resulting allocation patterns for implementation in practice. Thus, instead of a problem with a continuum of alternatives, we eventually consider a finite number of alternatives under several conflicting performance criteria. The study particularly illustrates the significance of mathematical modelling in the power game between globally operating product divisions and locally operating national organizations.
Advances in computer and communications technology have led to increased use of distributed computer systems which utilize communications channels to interconnect geographically separated users, computer facilities, a...
详细信息
Advances in computer and communications technology have led to increased use of distributed computer systems which utilize communications channels to interconnect geographically separated users, computer facilities, and data files into integrated information networks. In designing and controlling such a system, one must decide on the number and location of computer facilities, the allocation of multiple data files to facilities, and the user access paths to the data files. A mixed-integer programming formulation and dual-based solution procedure for this problem are described, and the results of computational experiments with realistic-sized problems are reported. Optimal solutions for problems with approximately 2,000 integer decision variables and 76,000 continuous decision variables are found in less than 30 CPU seconds, demonstrating the large-scale capability of the model and algorithm. The problem formulation generalizes Casey's File Allocation Problem to include the location of multiple files and computer facilities in a single planning model.
This paper concerns the development and implementation of a pilot Decision Support System for the bottleneck packaging facilities of a large dairy company. The planning and scheduling problem has been decomposed into ...
详细信息
This paper concerns the development and implementation of a pilot Decision Support System for the bottleneck packaging facilities of a large dairy company. The planning and scheduling problem has been decomposed into two levels: a tactical and operational control level. On the tactical level a feasible (daily) 'master production schedule' of the orderbook is determined. A mixedinteger Linear programming model is the basis for making this schedule. On the operational control level two sequencing subproblems have to be solved. For the solution of these subproblems well-known heuristics have been used.
This paper presents a mathematical model to load the existing maintenance/repair capacity with low-demand large items that are classified for various reasons. The objective is to minimize the lost sales cost while ens...
详细信息
This paper presents a mathematical model to load the existing maintenance/repair capacity with low-demand large items that are classified for various reasons. The objective is to minimize the lost sales cost while ensuring that no job is left unfinished. This model could be used in making scheduling decisions involving expensive and classified items that must be delivered by a self-imposed common due date. A sample problem is provided.
This paper proposes mathematical programming models for machine requirements planning in a multiproduct, multimachine, multistage manufacturing environment. Two models are developed, a mixed-integer linear programming...
详细信息
This paper proposes mathematical programming models for machine requirements planning in a multiproduct, multimachine, multistage manufacturing environment. Two models are developed, a mixed-integer linear programming model that takes into consideration factors of production such as resource and budget constraints, and a goal programming model that takes conflicting goals into account. Validation of the models is demonstrated by way of application to a computer hard disc manufacturing plant. The efficacy of the models and their results are discussed in a comparative manner.
This paper outlines a modelling framework for assessing the implication of long term fisheries policy decisions. It illustrates an approach to model building that begins with establishment of a matrix reflecting the b...
详细信息
This paper outlines a modelling framework for assessing the implication of long term fisheries policy decisions. It illustrates an approach to model building that begins with establishment of a matrix reflecting the basic features of the fisheries sector and then proceeds to incorporate these features into an integerprogramming model. The model estimates the real cost of alternative policies and takes into account the various biological and economic constraints to production. The model has provided a valuable tool for the assessment of different policy options for Kuwait's fisheries sector. Such options involved establishing the most appropriate way to maximize fresh-fish self-sufficiency while reconciling the production from multi-gear multi-species capture fisheries with the need to develop an aquaculture industry in the country.
暂无评论