A linear programming embedded probabilistic tabu search for the unequal-area facility layout problem with flexible bays

In this paper, a probabilistic tabu search (PTS) approach is proposed to solve the facility layout problem (FLP) with unequal area departments. For the representation, the flexible bay structure (FBS), which is a very common layout in many manufacturing and retail facilities, is used. In this paper, the FBS is relaxed by allowing empty spaces within bays, which results in more flexibility in assigning departments into bays. In addition, departments are allowed to be located more freely within the bays, and they can have different side lengths as long as they are within the bay boundaries and do not overlap. To achieve these goals, department shapes and their locations within bays are determined LP. A PTS approach is developed to search an overall layout structure that describes relative positions of departments for the relaxed-FBS (RFBS). The proposed LP embedded PTS–RFBS approach is used to solve thirteen FLP instances from the literature with varying sizes. The comparative results show that this approach is very promising and able to find new best solutions for several test problems.     

Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers

This paper presents new mixed integer programming formulations for scheduling of a flexible flow line with blocking. The flexible flow line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. The line produces several different product types and each product must be processed by, at most, one machine in each stage. A product which has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine a production schedule for all products so as to complete the products in a minimum time. The basic mixed integer programming formulations have been enhanced to model blocking scheduling with alternative processing routes where for each product a set of routes is available for processing. A reentrant flow line where a product visits a set of stages more than once is also considered. Numerical examples are presented to illustrate applications of the various models proposed.     

Strong formulations for mixed integer programming: A survey

We attempt to motivate and survey recent research on the use of strong valid inequalities and reformulation to solve mixed integer programming problems.     

Cutting plane algorithms for the inverse mixed integer linear programming problem

We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal.     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

A convex optimisation framework for the unequal-areas facility layout problem

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present a convex-optimisation-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical programming models. The first model is a convex relaxation of the layout problem that establishes the relative position of the departments within the facility, and the second model uses semidefinite optimisation to determine the final layout. Aspect ratio constraints, frequently used in facility layout methods to restrict the occurrence of overly long and narrow departments in the computed layouts, are taken into account by both models. We present computational results showing that the proposed framework consistently produces competitive, and often improved, layouts for well-known large instances when compared with other approaches in the literature.     

A branch-and-bound algorithm for 0–1 parametric mixed integer programming

A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained.     

A single-level reformulation of mixed integer bilevel programming problems

This paper focuses on the single-level reformulation of mixed integer bilevel programming problems (MIBLPP). Due to the existence of lower-level integer variables, the popular approaches in the literature such as the first-order approach are not applicable to the MIBLPP. In this paper, we reformulate the MIBLPP as a mixed integer mathematical program with complementarity constraints (MIMPCC) by separating the lower-level continuous and integer variables. In particular, we show that global and local minimizers of the MIBLPP correspond to those of the MIMPCC respectively under suitable conditions.     

Mixed integer goal programming models for the flexible job-shop scheduling problems with separable and non-separable sequence dependent setup times

The optimization problem addressed in this paper is an advanced form of the flexible job shop scheduling problem (FJSP) which also covers process plan flexibility and separable/non-separable sequence dependent setup times in addition to routing flexibility. Upon transforming the problem into an equivalent network problem, two mixed integer goal programming models are formulated. In the first model (Model A) the sequence dependent setup times are non-separable. In the second one (Model B) they are separable. Model B is obtained from Model A with a minor modification. The formulation of the models is described on a small sized numerical example and the solutions are interpreted. Finally, computational results are obtained on test problems.     

A mixed integer programming model for advanced planning and scheduling (APS)

This paper presents a mixed integer programming (MIP) model which succeeds in a system integration of the production planning and shop floor scheduling problems. The proposed advanced planning and scheduling (APS) model explicitly considers capacity constraints, operation sequences, lead times and due dates in a multi-order environment. The objective of the model is to seek the minimum cost of both production idle time and tardiness or earliness penalty of an order. The output of the model is operation schedules with order starting time and finish time. Numerical result shows that the suggested APS model can favorably produce optimal schedules.     

Complete mixed integer linear programming formulations for modularity density based clustering

Modularity density maximization is a clustering method that improves some issues of the commonly used modularity maximization approach. Recently, some Mixed-Integer Linear Programming (MILP) reformulations have been proposed in the literature for the modularity density maximization problem, but they require as input the solution of a set of auxiliary binary Non-Linear Programs (NLPs). These can become computationally challenging when the size of the instances grows. In this paper we propose and compare some explicit MILP reformulations of these auxiliary binary NLPs, so that the modularity density maximization problem can be completely expressed as MILP. The resolution time is reduced by a factor up to two order of magnitude with respect to the one obtained with the binary NLPs.     

A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem

In this paper, we consider an extension of the Markovitz model, in which the variance has been replaced with the Value-at-Risk. So a new portfolio optimization problem is formulated. We showed that the model leads to an NP-hard problem, but if the number of past observation T or the number of assets K are low, e.g. fixed to a constant, polynomial time algorithms exist. Furthermore, we showed that the problem can be formulated as an integer programming instance. When K and T are large and α^VaR is small—as common in financial practice—the computational results show that the problem can be solved in a reasonable amount of time.     

A note on “A new local and global optimization method for mixed integer quadratic programming problems” by G.Q. Li et al.

In this comment, we preset a minor mistake in typing which is made in “A new local and global optimization method for mixed integer quadratic programming problems” by G.Q. Li et al.     

Models and algorithms to improve earthwork operations in road design using mixed integer linear programming

In road construction, earthwork operations account for about 25% of the construction costs. Existing linear programming models for earthwork optimization are designed to minimize the hauling costs and to balance the earth across the construction site. However, these models do not consider the removal of physical blocks that may influence the earthwork process. As such, current models may result in inaccurate estimates of optimal earthwork costs, leading to poor choices in road design. In this research, we extend the classical linear program model of earthwork operations to a mixed integer linear program model that accounts for blocks. We examine the economic impact of incorporating blocks via mixed integer linear programming, and find significant savings for most road designs in our test-set. However, the resulting model is considerably harder to solve than the original linear program. Based on structural observations, we introduce a set of algorithms that theoretically reduce the solving time of the model. We confirm this reduction in solve time with numerical experiments.     

Integrating local search techniques into mixed integer programming

We survey the main results of the authors PhD thesis that was supervised by Claude Le Pape (ILOG, France) and Philippe Michelon (Université dAvignon, France) and has been defended in June 2004. The dissertation is written in French and is available from the author. It introduces several strategies for integrating local search techniques into mixed integer programming, with an emphasis on generic algorithms.Received: June 2004, MSC classification: 90C11, 90C59     

An algorithm for mixed integer optimization

This paper introduces a new algorithm for solving mixed integer programs. The core of the method is an iterative technique for changing the representation of the original mixed integer optimization problem. Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202.Mathematics Subject Classification (1991):90C11     

A note on “A mixed integer programming model for advanced planning and scheduling (APS)”

In a recent paper, Chen and Ji [Chen, K., Ji, P., 2007. A mixed integer programming model for advanced planning and scheduling (APS). European Journal of Operational Research 181, 515–522] develop a mixed integer programming model for advanced planning and scheduling problem that considers capacity constraints and precedence relations between the operations. The orders require processing of several operations on eligible machines. The model presented in the above paper works for the case where each operation can be processed on only one machine. However, machine eligibility means that only a subset of machines are capable of processing a job and this subset may include more than one machine. We provide a general model for advanced planning and scheduling problems with machine eligibility. Our model can be used for problems where there are alternative machines that an operation can be assigned to.     

Evaluation of mathematical models for flexible job-shop scheduling problems

With the rapid development in computer technologies, mathematical programming-based technique to solve scheduling problems is significantly receiving attention from researchers. Although, it is not efficient solution method due to the NP-hard structure of these problems, mathematical programming formulation is the first step to develop an effective heuristic. Numerous comparative studies for variety scheduling problems have appeared over the years. But in our search in literature there is not an entirely review for mathematical formulations of flexible job shop scheduling problems (FJSP). In this paper, four the most widely used formulations of the FJSP are compiled from literature and a time-indexed model for FJSP is proposed. These formulations are evaluated under three categories that are distinguished by the type of binary variable that they rely on for using of sequencing operations on machines. All five formulations compared and results are presented.