混合整数双层线性规划的全局优化算法

本文讨论了上层决策变量为整数变量、下层决策变量为连续变量的混合整数双层线性规划问题,利用其可行解均落在约束域边界上的性质,提出了一种求解混合整数双层线性规划全局最优解的算法,并举例说明了算法的执行过程。     

A generalized interval fuzzy mixed integer programming model for a multimodal transportation problem under uncertainty

A generalized interval fuzzy mixed integer programming model is proposed for the multimodal freight transportation problem under uncertainty, in which the optimal mode of transport and the optimal amount of each type of freight transported through each path need to be decided. For practical purposes, three mathematical methods, i.e. the interval ranking method, fuzzy linear programming method and linear weighted summation method, are applied to obtain equivalents of constraints and parameters, and then a fuzzy expected value model is presented. A heuristic algorithm based on a greedy criterion and the linear relaxation algorithm are designed to solve the model.     

A comparison of mixed integer programming formulations of the capacitated lot-sizing problem

We propose a novel mixed integer programming formulation for the capacitated lot-sizing problem with set-up times and set-up carryover. We compare our formulation to two earlier formulations, the Classical and Modified formulations, and a more recent formulation due to Suerie and Stadtler. Extensive computational experiments show that our formulation consistently outperforms the Classical and Modified formulations in terms of CPU time and solution quality. It is competitive with the Suerie–Stadtler (S&S) formulation, but outperforms all other formulations on the most challenging instances, those with low-capacity slack and a dense jobs matrix. We show that some of the differences in the performance of these various formulations arise from their different use of binary variables to represent production or set-up states. We also show that the LP relaxation of our Novel formulation provides a tighter lower bound than that of the Modified formulation. Our experiments demonstrate that, while the S&S formulation provides a much tighter LP bound, the Novel formulation is better able to exploit the intelligence of the CPLEX solution engine.     

Production scheduling with outsourcing scenarios: a mixed integer programming and efficient solution procedure

When market demand exceeds the company's capacity to manufacture, outsourcing is commonly considered as an effective alternative option. In traditional scheduling problems, processing of received orders is just possible via in-house resources, while in practice, outsourcing is frequently found in various manufacturing industries, especially in electronics, motor and printing companies. This paper deals with the scheduling problem, minimising the cost of outsourcing and a scheduling measure represented by weighted mean flow time, in which outsourcing of manufacturing operations is allowed through subcontracts. Each order can be either scheduled for in-house production or outsourced to an outside supplier in order to meet customer due dates. In this problem, not only should the sequence of orders be determined, but also decision on picking the jobs for outsourcing, selecting the appropriate subcontractor, and scheduling of the outsourced orders are considered as new variables. To formulate the given problem, four different outsourcing scenarios are derived and mixed integer programming models are developed for each one separately. Furthermore, to solve the suggested problem, a computationally effective team process algorithm is devised and then a constraint handling technique is embedded into the main algorithm in order to ensure satisfaction of customer due dates. Numerical results show that the suggested approach possesses high global solution rates as well as fast convergence.     

Heuristics for the integer one-dimensional cutting stock problem: A computational study

In this paper the problem of generating integer solutions to the standard one-dimensional cutting stock problem is treated. In particular, we study a specific class of heuristic approaches that have been proposed in the literature, and some straightforward variants. These methods are compared with respect to solution quality and computing time. Our evaluation is based on having solved 4,000 randomly generated test problems. Not only will it be shown that two methods are clearly superior to the others but also that they solve almost any instance of the standard one-dimensional cutting stock problem to an optimum.     

The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation,a Benders decomposition and a CP-based algorithm

This paper addresses a variant of two-dimensional cutting problems in which rectangular small pieces are obtained by cutting a rectangular object through guillotine cuts. The characteristics of this variant are (i) the object contains some defects, and the items cut must be defective-free; (ii) there is an upper bound on the number of times an item type may appear in the cutting pattern; (iii) the number of guillotine stages is not restricted. This problem commonly arises in industrial settings that deal with defective materials, e.g. either by intrinsic characteristics of the object as in the cutting of wooden boards with knotholes in the wood industry, or by the manufacturing process as in the production of flat glass in the glass industry. We propose a compact integer linear programming (ILP) model for this problem based on the discretisation of the defective object. As solution methods for the problem, we develop a Benders decomposition algorithm and a constraint-programming (CP) based algorithm. We evaluate these approaches through computational experiments, using benchmark instances from the literature. The results show that the methods are effective on different types of instances and can find optimal solutions even for instances with dimensions close to real-size.     

A mixed integer linear programming solution for single hoist multi-degree cyclic scheduling with reentrance

This article considers single hoist multi-degree cyclic scheduling problems with reentrance. Time window constraints are also considered. Firstly, a mixed integer programming model is formulated for multi-degree cyclic hoist scheduling without reentrance, referred to as basic lines in this article. Two valid inequalities corresponding to this problem are also presented. Based on the model for basic lines, an extended mixed integer programming model is proposed for more complicated scheduling problems with reentrance. Phillips and Unger's benchmark instance and randomly generated instances are applied to test the model without reentrance, solved using the commercial software CPLEX. The efficiency of the model is analysed based on computational time. Moreover, an example is given to demonstrate the effectiveness of the model with reentrance.     

Multiple-choice knapsack-based heuristic algorithm for the two-stage two-dimensional cutting stock problem in the paper industry

This study examines a two-stage two-dimensional cutting stock problem encountered by a paper mill company. The problem includes various machine-related and operational constraints based on real-world situations. Paper products are manufactured using two major cutting processes. Each cutting machine has a specific minimum and maximum width for input and output rolls and is limited by the maximum number of rolls it can cut at the same time. A mathematical model is presented to formally address the problem and an efficient multiple-choice knapsack-based heuristic algorithm is proposed to solve the problem. To demonstrate the efficiency of the proposed heuristic algorithm, computational experiments are conducted on test data-set generated from real-world data provided by a large paper mill company in the Republic of Korea.     

A 0-1 integer programming model and solving strategies for the slab storage problem

We consider the slab storage problem (SSP) in slab yard operations. A set of slabs enter a slab yard in a specific order. A proper stack needs to be selected for each inbound slab, so that the number of relocations in the subsequent retrieval stage is minimised. We present a 0-1 integer programming model of the SSP that minimises the lower bound of the number of relocations. Four solving strategies are derived from several interesting properties of the mathematical model to speed up the solving process of the model. Making use of randomly generated instances and practical instances, we testify the effectiveness of the solving strategies and study the influence of problem parameters on the computational time of the model. Computational results show that the solving strategies can effectively reduce the computational time of the model and is applicable in medium-sized practical instances.     

A novel integer programming formulation with logic cuts for the U-shaped assembly line balancing problem

U-shaped assembly lines are regarded as an efficient configuration in Just-In-Time manufacturing. Balancing the workload in these lines is an unsolved problem that attracted significant research within the past two decades. We present a novel integer programming formulation for U-shaped line balancing problems, where cycle time, the interval between two consecutive outputs, is known and the aim is to minimize the number of workstations. To enhance the efficiency of the LP relaxation of the new formulation, we present three types of logic cuts (assignable-station-cuts, task-assignment-cuts and knapsack-cuts) that exploit the inherent logic of the problem structure. The new formulation and logic cuts are tested on an extensive set of benchmark problems to provide a comparative analysis with the existing models in the literature. The results show that our novel formulation augmented by assignable-station-cuts is significantly better than the previous formulations.     

A mixed-integer linear programming model for integrated production and preventive maintenance scheduling in the capital goods industry

The scheduling literature is extensive, but much of this work is theoretical and does not capture the complexity of real world systems. Capital goods companies produce products with deep and complex product structures, each of which requires the coordination of jobbing, batch, flow and assembly processes. Many components require numerous operations on multiple machines. Integrated scheduling problems simultaneously consider two or more simultaneous decisions. Previous production scheduling research in the capital goods industry has neglected maintenance scheduling and used metaheuristics with stochastic search that cannot guarantee an optimal solution. This paper presents a novel mixed integer linear programming model for simultaneously solving the integrated production and preventive maintenance scheduling problem in the capital goods industry, which was tested using data from a collaborating company. The objective was to minimise total costs including: tardiness and earliness penalty costs; component and assembly holding costs; preventive maintenance costs; and set-up, production, transfer and production idle time costs. Thus, the objective function and problem formulation were more extensive than previous research. The tool was successfully tested using data obtained from a collaborating company. It was found that the company’s total cost could be reduced by up to 63.5%.     

Dynamic quality and pricing decisions in customer-intensive service systems with online reviews

In this paper, we investigate dynamic quality and pricing decisions for customer-intensive service systems with online reviews. We construct a dynamic programming model to determine the optimal quality and pricing strategies. We find that with online reviews, the supplier is forced to provide a higher quality at a higher price for fewer customers, especially when the customer intensity is high. Interestingly, although online reviews deliver quality information for later consumers, the provided quality may decrease over time. Next, we compare the optimal strategies with those of models of either quality flexibility or pricing flexibility, respectively, to examine the merits of our developed model of both quality and pricing flexibilities. The comparison results demonstrate that our model can achieve higher profits, and the advantages of our model increase with the number of periods. In addition, quality (pricing) flexibility is more valuable when consumers are more sensitive to service price (quality). Furthermore, we compare our formulated model with the model for a regular service system, and we illustrate that the optimal quality and pricing strategies in our system are quite different from those of the regular service system.     

Cloud manufacturing service composition and optimal selection with sustainability considerations: a multi-objective integer bi-level multi-follower programming approach

The process of service composition and optimal selection (SCOS) is an important issue in cloud manufacturing (CMfg). However, the current studies on CMfg and SCOS have generally focused on optimising the allocation of resources against quality of service (QoS), in terms of e.g. cost, quality, and time. They have seldom taken the perspective of sustainability into discussion, although sustainability is indispensable in the CMfg environment. Addressing this gap, we aim to (1) propose a comprehensive method to assess the sustainability of cloud manufacturing (SoM) in terms of the economic, environmental, and social aspects; (2) establish a multi-objective integer bi-level multi-follower programming (MOIBMFP) model to simultaneously maximise SoM and QoS from the perspectives of both platform operator and multiple service demanders; and (3) design a hybrid particle swarm optimisation algorithm to solve the proposed MOIBMFP model. The experimental results show that the proposed algorithm is more feasible and effective than the typical multi-objective particle swarm optimisation algorithm when solving the proposed model. In other words, the proposed model and algorithm suggest better alternatives to meet the needs of the platform operator and service demanders in the CMfg environment.     

Exact and approximate algorithms for the multi-period procurement problem where dedicated supplier capacity can be reserved

This paper is concerned with a multi-period inventory problem where the demand and the supplier capacity of a given key resource are discrete random variables with known probability distribution. The procurement manager has to answer two types of questions: how much supplier quantity to reserve for each period (where all of these reservations have to madeprior to the start of the first period) and how large an order quantity to use at start of each period. An exact procedure, based on branch and bound and dynamic programming, as well as various heuristic methods to solve the problem are presented in this paper. Heuristic methods are shown to perform extremely well in the sense that they provide near optimal strategies while requiring much less computational effort than the exact method.     

Algorithms for the joint multitasking scheduling and common due date assignment problem

In this paper, we investigate a joint multitasking scheduling and common due date assignment problem on a single machine, for which examples can be found in product delivery process in logistics. Multitasking allows the machine to perform multiple tasks. The multitasking phenomenon has been observed in various practical domains, including manufacturing and administration. In multitasking settings, each waiting job interrupts a currently in-processing job, causing an interruption time and a switching time. In common due date assignment problems, the objective is to determine the optimal value of this due date with the purpose of minimising a total penalty function, which is associated with service quality. For the problem with general interruption functions, analytical properties are obtained to reduce the search space of the optimal solutions. For the cases with linear interruption functions, we develop a polynomial-time algorithm. Numerical experiments have been conducted to validate the efficiency of our proposed algorithm. Computational results also demonstrate an interesting phenomenon that in some cases, the optimal solutions under multitasking are superior to the counterparts without multitasking. Besides, we also devise a mixed integer programme for the cases with linear interruption function.     

A bilinear programming model and a modified branch-and-bound algorithm for production planning in steel rolling mills with substitutable demand

In this paper, we address an instance of the dynamic capacitated multi-item lot-sizing problem (CMILSP) typically encountered in steel rolling mills. Production planning is carried out at the master production schedule level, where the various end items lot sizes are determined such that the total cost is minimised. Through incorporating the various technological constraints associated with the manufacturing process, the integrated production–inventory problem is formulated as a mixed integer bilinear program (MIBLP). Typically, such class of mathematical models is solved via linearisation techniques which transform the model to an equivalent MILP (mixed integer linear program) at the expense of increased model dimensionality. This paper presents an alternative branch-and-bound based algorithm that exploits the special structure of the mathematical model to minimise the number of branches and obtain the bound at each node. The performance of our algorithm is benchmarked against that of a classical linearisation technique for several problem instances and the obtained results are reported.     

An efficient method for dynamic-demand joint replenishment problem with multiple suppliers and multiple vehicles

How to improve competitive edges to meet rapidly changing market environment and dynamic customer needs is critical for the survival and success of firms these days. A good supply chain and inventory management is a necessity in the intensive competitive market. This paper considers a dynamic-demand joint replenishment problem with multiple vehicle routing. The problem is first formulated as a mixed integer programming model with an objective to minimise total costs, which include ordering cost, purchase cost, production cost, transportation cost and holding cost, under a prerequisite that inventory shortage is prohibited in the system. A particle swarm optimisation model is proposed next to solve large-scale problems which are computationally difficult. A case study of a touch panel manufacturer is presented to examine the practicality of the models.