Search

This paper systematically constructs a multi-project and a multi-objective human resource scheduling mathematical model in construction projects and puts forward an improved genetic algorithm to solve it by aiming at the problems existing in the process of human resource scheduling and optimization. Specifically, first, the basic mathematical models of GPRs and resource-constrained construction project human resource scheduling problem (RCWSP/GPRs) are established, and the multi-project equilibrium problem is extended. Then, an improved inter-cluster separation (ICS) algorithm is proposed and used to solve the RCWSP/GPRs problem. Finally, on this basis, the mathematical model of multi-project and multi-objective human resource scheduling problem and the solution method based on multi-objective-integrated circuit are proposed. At the same time, the resource-constrained multi-project and multi-skill human resource scheduling problem and the integer programming mathematical model under the generalized priority relationship are proposed. Also, the simulation results verify the accuracy of the proposed algorithm and model. [ABSTRACT FROM AUTHOR]

Highlights • A new rigorous bilevel decomposition strategy for MILPs with strong linking constraints. • An extended cross decomposition method based on the bilevel decomposition strategy. • Application of the extended cross decomposition method to stochastic programming with CVaR constraints. • Case studies with a variety of scenario instances showing significant computational advantages of the proposed methods. Abstract Large-scale mixed-integer linear programming (MILP) problems, such as those from two-stage stochastic programming, usually have a decomposable structure that can be exploited to design efficient optimization methods. Classical Benders decomposition can solve MILPs with weak linking constraints (which are decomposable when linking variables are fixed) but not strong linking constraints (which are not decomposable even when linking variables are fixed). In this paper, we first propose a new rigorous bilevel decomposition strategy for solving MILPs with strong and weak linking constraints, then extend a recently developed cross decomposition method based on this strategy. We also show how to apply the extended cross decomposition method to two-stage stochastic programming problems with conditional-value-at-risk (CVaR) constraints. In the case studies, we demonstrate the significant computational advantage of the proposed extended cross decomposition method as well as the benefit of including CVaR constraints in stochastic programming. [ABSTRACT FROM AUTHOR]

In this paper the fairness of some methods of allocating seats in a proportional representation (PR) voting system is investigated. Different PR systems are in use throughout the democratic world, but the primary focus here is the method used in South Africa, namely the largest remainder method with a Droop quota. It is shown that as the number of parties increases, the number of lost votes (votes not used to allocate seats) increases when using this method. Other existing allocation methods are discussed and compared with each other as well as with three optimisation methods (based on mathematical programming) introduced in this paper. Applying these mathematical programming methods results in allocations that are more fair than the existing methods of seat allocation, if South African voting data are used. These mathematical models attempt to minimise a number of different measures of the deviation between the actual percentage of votes received and the percentage of seats allocated to a certain party. Ideally this deviation should be zero, but due to the discrete nature of seats this is virtually impossible to achieve. [ABSTRACT FROM AUTHOR]

This paper studies the single-hoist cyclic scheduling problem in electroplating systems with two extended features. One extension is that the products must visit some processing tanks more than once (multi-function tanks). Another is that more than one identical tank is used at some stages. These extensions are common in practical electroplating lines and can increase the lines' processing capacity. However, they make the hoist scheduling problem more complicated and little research has been done to optimize the hoist moves in such extended practical systems. In this paper, we develop a comprehensive mixed integer linear programming model to find optimal solutions to the single-hoist cyclic scheduling problem for electroplating lines with these extensions. Examples are given to demonstrate the effectiveness of the model in different types of problems. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of infeasibility of systems defined by convex inequality constraints, where some or all of the variables are integer valued. In particular, we provide a polynomial time algorithm to identify a set of all constraints which may affect a feasibility status of the system after some perturbation of the right-hand sides. We establish several properties of the irreducible infeasible sets and infeasibility sets in the systems with integer variables, proving in particular that all irreducible infeasible sets and infeasibility sets are subsets of the set of constraints critical to feasibility. Furthermore, the well-known Bohnenblust-Karlin-Shapley Theorem, which requires that a system of convex inequality constraints must be defined over a compact convex set, is generalized to convex systems without the assumption on compactness of the convex region. Extension of the latter result to convex systems defined over the set of integers is also provided. [ABSTRACT FROM AUTHOR]

This paper is written with three objectives in mind. First, to point out that the problem of grouping, where a larger number of elements n are combined into m mutually exclusive groups (m ~n) should be recognized as a problem in Integer Programming, and that such recognition can help us in avoiding complete enumeration of stages in grouping from n to n - 1 ... to m, and of alternative possibilities in each stage. Second, to formulate mathematically some simple versions of the relevant Integer Programming Problem, so that the available computer codes can solve it. When the grouping attempts to minimize the within groups sums of squares, the so-called string property is proved to be necessary for the minimum (Lemma 1). It is shown that the string property can be exploited to write the non-linear within group sums of squares as a linear function (Lemma 2). An attempt is made to generalize the string property for the higher dimensional case. Third, to give some numerical examples to clarify the mathematical models and to illustrate the advantages of Integer Programming formulation by comparing with the numerical examples appearing in the literature [8], [13 ]. Zero-one programming where the integer variables can take values of zero or one only appears to be most efficient from the limited experience of the author. The paper is divided into three sections which closely correspond to the three objectives noted above. [ABSTRACT FROM AUTHOR]

This paper presents a nonlinear integer programming model to support the selection of maintenance strategies to implement on different segments of a railway network. Strategies are selected which collectively minimise the impact of sections' conditions on service, given network availability and budget constraints. Different metrics related to the network topology, sections' availability, service frequency, performance requirements and maintenance costs, are combined into a quantitative approach with a holistic view. The main contribution is to provide a simple yet effective modelling approach and solution method which are suitable for large networks and make use of standard solvers. Both an ad hoc heuristic solution and relaxation methods are developed, the latter enabling the quality of the heuristic solution to be estimated. The availability of railway lines is computed by exploiting the analogy with series–parallel networks. By varying the model parameters, a scenario analysis is performed to give insight into the influence of the system parameters on the selection of strategies, thus enabling more informed decisions. For its simple structure, the model is versatile to address similar problems arising in the maintenance of other types of networks, such as road and bridges networks, when deciding on the strategic allocation of maintenance efforts. • A nonlinear integer program is given to select maintenance strategies for railways. • A tailored heuristic enables fast solution to be found with standard solvers. • A tailored relaxation method enables the quality of the solution to be quantified. • Metrics of topology, availability, service, costs are combined in a holistic approach. • Effects of tracks redundancy, centrality, train frequency, availability are studied. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to point out that the integer programming model proposed by Eren and Güner [T. Eren, E. Güner, A bicriteria flowshop scheduling with a learning effect, Applied Mathematical Modelling 32 (2008) 1719–1733] is incorrect. We propose a mixed 0–1 programming model for the same scheduling problem based on their model. [Copyright &y& Elsevier]

Abstract: Since workers have an important role in doing jobs on machines, assignment of workers to cells becomes a crucial factor for full utilization of cellular manufacturing systems. This paper presents an integer mathematical programming model for the design of cellular manufacturing systems in a dynamic environment. The advantages of the proposed model are as follows: considering multi-period production planning, dynamic system reconfiguration, duplicate machines, machine capacity, available time of workers, and worker assignment. The aim of the proposed model is to minimize holding and backorder costs, inter-cell material handling cost, machine and reconfiguration costs and hiring, firing and salary costs. Computational results are presented by solving some examples. [ABSTRACT FROM AUTHOR]

Optimal reactive power flow applications often model large numbers of discrete shunt devices as continuous variables, which are rounded to their nearest discrete value at the final iteration. This can degrade optimality. This paper presents novel methods based on probabilistic and adaptive threshold approaches that can extend existing security constrained optimal reactive power flow methods to effectively solve large-scale network problems involving discrete shunt devices. Loss reduction solutions from the proposed techniques were compared to solutions from the mixed integer nonlinear mathematical programming algorithm (MINLP) using modified IEEE standard networks up to 118 buses. The proposed techniques were also applied to practical large-scale network models of Great Britain. The results show that the proposed techniques can achieve improved loss minimization solutions when compared to the standard rounding method. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we integrate at the tactical level two decision problems arising in container terminals: the berth allocation problem, which consists of assigning and scheduling incoming ships to berthing positions, and the quay crane assignment problem, which assigns to incoming ships a certain quay crane profile (i.e. number of quay cranes per working shift). We present two formulations: a mixed integer quadratic program and a linearization which reduces to a mixed integer linear program. The objective function aims, on the one hand, to maximize the total value of chosen quay crane profiles and, on the other hand, to minimize the housekeeping costs generated by transshipment flows between ships. To solve the problem we developed a heuristic algorithm which combines tabu search methods and mathematical programming techniques. Computational results on instances based on real data are presented and compared to those obtained through a commercial solver. [Copyright &y& Elsevier]

Recently, there has been a growing interest in reverse logistics due to environmental deterioration. Firms incorporate reverse flow to their systems for such reasons as ecological and economic factors, government regulations and social responsibilities. In this paper a new mixed integer mathematical model for a remanufacturing system, which includes both forward and reverse flows, is proposed and illustrated on a numerical example. The proposed model provides the optimal values of production and transportation quantities of manufactured and remanufactured products while solving the location problem of dissassembly, collection and distribution facilities. The model is validated by using a set of experimental data reflecting practical business situation. Sensitivity analysis of the model is also presented. [ABSTRACT FROM AUTHOR]

Abstract: With the economy continually moving towards retail and services, the size of the part-time workforce is increasing constantly. In this paper, we consider the problem of scheduling a workforce consisting entirely of part-time workers. The part-time workers have availabilities, preferences for the shifts, and also a seniority level. We propose an integer programming model to maximize employee satisfaction and to meet the demand requirements for each shift. The model is tested on randomly generated instances. The results demonstrate the effectiveness of branch-and-cut methods in reducing computation time. [Copyright &y& Elsevier]

Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically be solved in a reasonable amount of computing time. [ABSTRACT FROM AUTHOR]

In this paper two mathematical programming models, both with multiple objective functions, are proposed to solve four related categories of job scheduling problems. All four of these categories have the property that the duration of the jobs is dependent on the time of implementation and in some cases the preceding job. Furthermore, some jobs (restricted to subsets of the total pool of jobs) can, to different extents, run in parallel. In addition, not all the jobs need necessarily be implemented during the given time period. [ABSTRACT FROM AUTHOR]

Abstract: We show in this paper that the integer programming approach is well suited for solving the timetabling problem: the definition of the integer programming model is simple; its implementation is immediate by using, a mathematical programming language and an integer programming solver. The power of the integer programming approach allows us to extend the model in different interesting directions. A novel 0–1 integer programming formulation of the university timetabling problem is presented. The model provides constraints for a number of operational rules and requirements found in most academic institutions. [Copyright &y& Elsevier]

This paper discusses a method for scheduling Berth and Quay cranes, which are critical resources in port container terminals. An integer programming model is formulated by considering various practical constraints. A two-phase solution procedure is suggested for solving the mathematical model. The first phase determines the Berthing position and time of each vessel as well as the number of cranes assigned to each vessel at each time segment. The subgradient optimization technique is applied to obtain a near-optimal solution of the first phase. In the second phase, a detailed schedule for each Quay crane is constructed based on the solution found from the first phase. The dynamic programming technique is applied to solve the problem of the second phase. A numerical experiment was conducted to test the performance of the suggested algorithms. [ABSTRACT FROM AUTHOR]

The Generalized Vehicle Routing Problem (GVRP) is an extension of the classical Vehicle Routing Problem (VRP), in which we are looking for an optimal set of delivery or collection routes from a given depot to a number of customers divided into predefined, mutually exclusive, and exhaustive clusters, visiting exactly one customer from each cluster and fulfilling the capacity restrictions. This paper deals with a more generic version of the GVRP, introduced recently and called Selective Vehicle Routing Problem (SVRP). This problem generalizes the GVRP in the sense that the customers are divided into clusters, but they may belong to one or more clusters. The aim of this work is to describe a novel mixed integer programming based mathematical model of the SVRP. To validate the consistency of the novel mathematical model, a comparison between the proposed model and the existing models from literature is performed, on the existing benchmark instances for SVRP and on a set of additional benchmark instances used in the case of GVRP and adapted for SVRP. The proposed model showed better results against the existing models. [ABSTRACT FROM AUTHOR]