Apportionment methods and the Liu–Layland problem

The Liu–Layland periodic scheduling problem can be solved by the house monotone quota methods of apportionment. This paper shows that staying within the quota is necessary for any apportionment divisor method to solve this problem. As a consequence no divisor method, or equivalently no population monotone method, solves the Liu–Layland problem.     

Solving the generalized apportionment problem through the optimization of discrepancy functions

One of the ways to solve the classical apportionment problem (which has been studied chiefly in relation to the apportionment of seats in a chamber of representatives) is the optimization of a discrepancy function; although this approach seems very natural, it has been hardly used. In this paper, we propose a more general formalization of the problem and an optimization procedure for a broad class of discrepancy functions, study the properties of the procedure and present some examples in which it is applied.     

Solving the Unit Commitment Problem by a Unit Decommitment Method

In this paper, we present a unified decommitment method to solve the unit commitment problem. This method starts with a solution having all available units online at all hours in the planning horizon and determines an optimal strategy for decommitting units one at a time. We show that the proposed method may be viewed as an approximate implementation of the Lagrangian relaxation approach and that the number of iterations is bounded by the number of units. Numerical tests suggest that the proposed method is a reliable, efficient, and robust approach for solving the unit commitment problem.     

The Stochastic Location-Assignment Problem on a Tree

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.     

Heuristics for the Phylogeny Problem

A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The problem of finding a phylogeny with the minimum number of evolutionary steps (the so-called parsimony criterion) is one of the main problems in comparative biology. In this work, we study different heuristic approaches to the phylogeny problem under the parsimony criterion. New algorithms based on metaheuristics are also proposed. All heuristics are implemented and compared under the same framework, leading to consistent and thorough comparative results. Computational results are reported for benchmark instances from the literature.     

Postoptimality Analyses of the Transportation Problem

We develop here a new approach to postoptimality analyses of the transportation problem (TP) through the use of perturbation analysis. In contrast to the usual sensitivity analysis the proposed methods allow for simultaneous, independent (or dependent) perturbation of the supplies, demands and transportation rates cost from their nominal values whilst preserving the current optimal basis. The essential parts of the calculation involve the same manipulations as the solution algorithm used in solving the parametric perturbed supply-demand version of the nominal TP. Furthermore, the coefficient of the perturbed parameters in the optimal parametric cost function is used to indicate the existence of a cheaper (or equivalent cost) solution than the current optimal one by shipping more total goods. The proposed approach permits computation of the maximal allowable additional units and distribution of these extra units in a systematic manner. The proposed unified procedures are demonstrated by numerical examples.     

Mathematical programming modeling of the Response Time Variability Problem

The Response Time Variability Problem (RTVP) is a scheduling problem that has recently been defined in the literature. The RTVP has a broad range of real-life applications from manufacturing to services and information technology. A previous study developed a position exchange heuristic to apply to initial sequences for the RTVP, and a MILP (Mixed Integer Linear Programming) to obtain optimal solutions with a practical limit of 25 units to be scheduled. This paper aims to improve the best mathematical programming model developed thus far in order to solve larger instances up to 40 units to optimality. The contribution of this paper is 4-fold: (i) larger instances can be solved to optimality by the off the shelf standard software; (ii) the new optimal solutions of the RTVP can be used to compare the results of heuristic procedures; (iii) the importance of modeling is demonstrated, as well as the huge impact that reformulation, redundant constraints and the elimination of symmetries have on the efficiency of MILPs is clearly established; finally (iv) a challenge to develop a customized optimization algorithm to rival the MILP solution efficiency for the RTVP is put forward.     

Solving the Combined Zoning and Location Problem for Several Emergency Units

This paper discusses methods for the solution of the combined zoning and location problem for several emergency units. This is a stochastic optimization problem. The stochastic aspects include ordered preference of servers. A constraint of equal workload for the servers is also dealt with. Non-linear programming techniques are adapted for its solution.     

Modelling and solving the production rate variation problem (PRVP)

Several families of objective functions for the PRV problem (minimizing the variation in the rate at which different products are produced on an assembly line) are formalized, relationships between them are established and it is demonstrated that, in very general conditions, they can be optimized by solving an assignment problem or a polynomially bounded sequence of assignment problems.     

基于遗传算法的多目标可靠性优化

在元件的体积、重量和造价的共同约束下的多级串并联系统的可靠性优化问题是一个具有多局部极值的、非线性的、同时具有整数和实数变量的混合优化问题.将遗传算法和多目标可靠性分配问题相结合,对可靠性分配问题进行求解,得到较好效果,从而得出结论,遗传算法在求解多目标可靠性优化问题中是一种行之有效的方法.     

Problem solving activities of two middle school students with distinct levels of units coordination

The aim of this study is to investigate relationships between students’ arithmetical knowledge and their proportional reasoning. Two of seven students for whom we conducted clinical interviews were selected as participants in the study. An analysis of their solutions to four different types of multiplicative problems (equal sharing, reversible multiplicative relationship, fraction composition, and proportional relationship) was conducted. Based on the analysis, we found that the student who coordinated two three-level units structures prior to activity in the first three problem types could also solve the proportion problem using the units coordination. In contrast, the student who coordinated two three-level units structures only in activity in the first three problem types could not solve the proportion problem. Given the importance of units coordinating operations in solving diverse problems, implications for further research on students’ construction of proportional reasoning are discussed.     

A Simulated Annealing Genetic Algorithm for the Electrical Power Districting Problem

Due to a variety of political, economic, and technological factors, many national electricity industries around the globe are transforming from non-competitive monopolies with centralized systems to decentralized operations with competitive business units. A key challenge faced by energy restructuring specialists at the World Bank is trying to simultaneously optimize the various criteria one can use to judge the fairness and commercial viability of a particular power districting plan. This research introduces and tests a new algorithm for solving the electrical power districting problem in the context of the Republic of Ghana and using a random test problem generator. We show that our mimetic algorithm, the Simulated Annealing Genetic Algorithm, outperforms a well-known Parallel Simulated Annealing heuristic on this new and interesting problem manifested by the deregulation of electricity markets.     

Greatest remainder bi-proportional rounding and the Greek parliamentary elections of 2007

Matrix scaling is the problem of assigning values to the elements of a matrix that are proportional to a given input matrix. The assignment should fulfill a set of row- and column-sum requirements. We propose a new method that differs from divisor-type methods appeared until now in the literature. This method combines the largest remainder apportionment and bi-proportional rounding. Exhaustive application to the Greek parliamentary elections of 2007 justify our effort.     

The product rate variation problem and its relevance in real world mixed-model assembly lines

Production processes in a wide range of industries rely on modern mixed-model assembly systems, which allow an efficient manufacture of various models of a common base product on the same assembly line. In order to facilitate a just-in-time supply of materials, the literature proposes various sequencing problems under the term “level scheduling”, which all aim at evenly smoothing the part consumption induced by the production sequence over time. Among these approaches, the popular product rate variation (PRV) problem is considered to be an appropriate approximate model, if either (i) all products require approximately the same number and mix of parts or (ii) part usages of all products are (almost completely) distinct. These statements are (iii) further specified by analytical findings, which prove the equivalence of product and material oriented level scheduling under certain conditions. These three prerequisites commonly cited in the literature when justifying the practical relevance of the PRV are evaluated by means of three simple computational experiments and are then discussed with regard to their relevance in practical settings. It is concluded that the PRV is in fact inappropriate for use in today’s real world mixed-model assembly systems.     

On the complexity of the Unit Commitment Problem

Annals of Operations Research - This article analyzes how the Unit Commitment Problem (UCP) complexity evolves with respect to the number n of units and T of time periods. A classical reduction...     

席位分配问题的有界整数变量规划模型及其应用

对席位分配问题进行再研究,以公平分摊性公理为基础,分别从议员公平性、公民公平性和州公平性的角度出发建立了三个相应的数学模型,它们都可归结为有界整数变量非线性规划模型.给出三个席位分配模型的一个统一算法,算法简单有效.最后给出了模型应用实例.     

物流服务供应链订单分配优化及其遗传算法

针对物流服务供应链订单分配问题中,物流服务集成商通常会按照所分配的订单价值向分包商收取一定比例交易费用的特点,设定交易费用为交易额的线性函数,构建了新的物流服务供应链订单分配优化混合整数规划模型,其优化目标为最小化交易费用、采购费用、短缺服务与延迟供给的物流能力数量。鉴于问题的NP-hard特性,设计了相应的遗传算法,并结合基于优先权的启发式规则避免了大量非法初始解的出现。实验算例表明所建立的模型能够反映物流服务供应链订单分配过程中的线性交易费用因素,其所设计的算法能够在可接受的时间内获得质量较高的满意解,并且对于大规模订单分配优化问题,遗传算法的求解时间与求解结果要优于LINGO软件。     

Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem

In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop scheduling problem. This is mainly guided by the observation that constraint propagation is more effective for small problem instances. Roughly speaking, the algorithm consists of deducing operation sequences that are likely to occur in an optimal solution of the job shop scheduling problem (JSP).The algorithm for which the name edge-guessing procedure has been chosen – since with respect to the job shop scheduling problem (JSP) the deduction of machine sequences is mainly equivalent to orienting edges in a disjunctive graph – can be applied in a preprocessing step, reducing the solution space, thus speeding up the overall solution process. In spite of the heuristic nature of edge-guessing, it still leads to near-optimal solutions. If combined with a heuristic algorithm, we will demonstrate that given the same amount of computation time, the additional application of edge-guessing leads to better solutions. This has been tested on a set of well-known JSP benchmark problem instances.     

Vector and matrix apportionment problems and separable convex integer optimization

The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.     

A Note on the Joint Replenishment Problem under Constant Demand

This note considers the joint replenishment inventory problem for N items under constant demand. The frequently-used cyclic strategy (T; k₁, …, k _N ) is investigated: a family replenishment is made every T time units and item i is included in each k _i th replenishment. Goyal proposed a solution to find the global optimum within the class of cyclic strategies. However, we will show that the algorithm of Goyal does not always lead to the optimal cyclic strategy. A simple correction is suggested.