The maximum capture per unit cost location problem

This paper considers the problem of siting p new facilities of an entering firm to a competitive market so as to maximize the market share captured from competitors per unit cost. We first formulate the problem as a mixed 0-1 fractional programming model, in which we incorporate the fixed cost and transportation cost. The model can deal with the case where some demand nodes have two or more possible closest servers. We then re-formulate the problem as a 0-1 mixed integer linear program. We use a one-opt heuristic algorithm based on the Teitz-Bart method to obtain feasible solutions and compare them with the optimal solutions obtained by a branch-and-bound algorithm. We conduct computational experiments to evaluate the two algorithms. The results show that both algorithms can solve the model efficiently and the model is integer-friendly. We discuss other computational results and provide managerial insights.     

Order acceptance and scheduling in a two-machine flowshop

We study the order acceptance and scheduling problem in a two-machine flowshop. The firm receives a pool of orders before a planning period, each of which is characterized by revenue, processing times on machines 1 and 2, a due date, and a tardiness penalty. The firm seeks to decide on the orders to accept and schedule the accepted orders so as to maximize the total net revenue. We formulate the problem as mixed-integer linear programming models, and develop a heuristic and a branch-and-bound (B&B) algorithm based on some derived dominance rules and relaxation techniques. We assess the performance of the B&B algorithm and the heuristic via computational experiments. The computational results show that the B&B algorithm can solve problem instances with up to 20 jobs within a reasonable time while the heuristic is efficient in approximately solving large instances of the problem.     

Job rotation in assembly lines employing disabled workers

In this paper we consider the programming of job rotation in the assembly line worker assignment and balancing problem. The motivation for this study comes from the designing of assembly lines in sheltered work centers for the disabled, where workers have different task execution times. In this context, the well-known training aspects associated with job rotation are particularly desired. We propose a metric along with a mixed integer linear model and a heuristic decomposition method to solve this new job rotation problem. Computational results show the efficacy of the proposed heuristics.     

多参数线性规划

本文讨论了多个参数的线性规划问题。建立了参数的最优比例结构的概念,并给出了确定这种比例的一种方法。     

A tabu search algorithm for the relocation problem in a warehousing system

Relocation of items in a warehousing system is usually used when the handling machines become the bottleneck. This paper addresses the optimization problem of relocation in a warehouse with dynamic operating policy. An integer linear programming formulation is proposed. A two-stage heuristic method is developed to generate an initial solution. A tabu search algorithm is proposed to improve the solution. Two relocation policies are studied and their performances are compared.     

Lot sizes in a capacity constrained facility—a simulation study of stationary stochastic demand

This paper considers the scheduling of several different items on a single machine, in literature known as the economic lot scheduling problem, ELSP. One of the characteristics of this problem is that the demand rate is deterministic and constant. However, in a practical situation demand usually varies. In this paper we examine if a deterministic model can be used if demand is stationary stochastic. A dynamic programming approach from Bomberger (Manage. Sci. 12(11) (1966) 778) and a heuristic method from Segerstedt (Int. J. Production Econom. 59(1–3) (1999) 469) are used to calculate lot sizes for four items. The production of these items is simulated with different variations in demand rates. Our conclusion is that a deterministic model of this kind can be used in a practical situation where the demand rate is stationary stochastic, but the models must be complemented by a decision rule; which item to produce and when to produce it. In our tests the heuristic method and the dynamic programming approach perform rather similarly with respect to costs and inventory levels, but the dynamic programming approach results in more backorders when there is small variation in demand rates. This study indicates that the model used for determination of lot sizes is of less importance than the decision rule used for identification of the item to produce and when to produce it.     

逆矩阵[B+△B]~(-1)的迭代算法

本文在建立极端稀疏矩阵及其 J 逆概念和算法的基础上,讨论了结构参数改变的线性规划问題中由已有的 B~(-1)出发计算[B+△B]~(-1)的迭代算法.它特别适用于△B 包含连续变参数的情形.     

Incorporating uncertainty into a supplier selection problem

Supplier selection is an important strategic supply chain design decision. Incorporating uncertainty of demand and supplier capacity into the optimization model results in a robust selection of suppliers. A two-stage stochastic programming (SP) model and a chance-constrained programming (CCP) model are developed to determine a minimal set of suppliers and optimal order quantities with consideration of business volume discounts. Both models include several objectives and strive to balance a small number of suppliers with the risk of not being able to meet demand. The SP model is scenario-based and uses penalty coefficients whereas the CCP model assumes a probability distribution and constrains the probability of not meeting demand. Both formulations improve on a deterministic mixed integer linear program and give the decision maker a more complete picture of tradeoffs between cost, system reliability and other factors. We present Pareto-optimal solutions for a sample problem to demonstrate the benefits of the SP and CCP models. In order to describe the tradeoffs between costs and risks in an analytical form, we use multi-parametric programming techniques to more completely analyze the alternative Pareto-optimal supplier selection solutions in the CCP model. This analysis gives insights into the robustness of the solutions with respect to number of suppliers, costs and probability of not meeting demand.     

A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems—A case study for solar cell industry

This paper studies a solar cell industry scheduling problem which is similar to the traditional hybrid flow shop scheduling (HFS). In a typical HFS with parallel machines problem, the allocation of machine resources for each order should be scheduled in advance and then the optimal multiprocessor task scheduling in each stage could be determined. However, the challenge in solar cell manufacturing is the number of machines can be dynamically adjusted to complete the job within the shortest possible time. Therefore, the paper addresses a multi-stage HFS scheduling problem with characteristics of parallel processing, dedicated machines, sequence-independent setup time, and sequence-dependent setup time. The objective is to schedule the job production sequence, number of sublots, and dynamically allocate sublots to parallel machines such that the makespan time is minimized. The problem is formulated as a mixed integer linear programming (MILP) model. A hybrid approach based on the variable neighborhood search and particle swarm optimization (VNPSO) is developed to obtain the near-optimal solution. Preliminary computational study indicates that the developed VNPSO not only provides good quality solutions within a reasonable amount of time but also outperforms the classic branch and bound method and the current industry heuristic practiced by the case company.     

GAN-MP hybrid heuristic algorithm for non-convex portfolio optimization problem

Abstract

During recent decades, the traditional Markowitz model has been extended for asset cardinality, active share, and tracking-error constraints, which were introduced to overcome the drawbacks of the original Markowitz model. The resulting optimization problems, however, are often very difficult to solve, whereas those of the original Markowitz model are easily solvable. In order to resolve the portfolio optimization problem for the new extensions, we developed a novel heuristic algorithm that combines GAN (Generative Adversarial Networks) with mathematical programming: the GAN-MP hybrid heuristic algorithm. To the best of our knowledge, this is the first attempt to bridge neural networks (NN) and mathematical programming to tackle a real-world portfolio optimization problem. Computational experiments with real-life stock data show that our algorithm significantly outperforms the existing non-linear optimization solvers.     

Stochastic single-source capacitated facility location model with service level requirements

A stochastic version of single-source capacitated facility location problem is considered. A set of capacitated facilities is to be selected to provide service to demand points with stochastic demand at the minimal total cost. The facilities have service level requirements modeled by chance constraints. For Poisson demand, the problem is proved equivalent to a known solvable deterministic problem. For Normally distributed demand, it is equivalent to a deterministic mixed integer non-linear programming problem. A hybrid heuristic of Lagrangean relaxation with a single-customer-multi-exchange heuristic is embedded within a branch-and-bound framework to find upper and lower bounds for this problem. From test instances created from benchmark problems (10–20 facilities and 50 demand nodes) and real-life data on the deterministic problem, the gap between the bounds is within 6.5% with an average of 2.5%.     

基于效应的随机灰规划模型和应用

为了解决同时含有随机因素和灰色因素的不确定规划问题,通过结合区间灰数所属区间两个端点的随机性,给出随机区间灰数和随机区间灰函数的定义,提出了随机灰规划模型。通过综合效应函数理论用随机变量期望值和方差综合量化表示灰数所属区间的两个端点值。应用该理论对综合量化后的两个端点值继续进行综合量化,从而将随机灰规划转化为确定型规划问题。应用遗传算法进行求解。通过综合效应函数的理念,综合随机变量的期望和方差,同时综合区间灰数的区间因素,将随机灰规划数学模型转化为确定型规划模型即基于效应的随机灰规划模型。通过选取不同的综合效应函数,得到了关于不同决策意识下的随机灰规划的最优解。这个方法可为决策者进行不确定决策提供参考。     

Inventory control in a two-level supply chain with risk pooling effect

We consider an inventory control problem in a supply chain consisting of a single supplier, with a central distribution center (CDC) and multiple regional warehouses, and multiple retailers. We focus on the problem of selecting warehouses to be used among a set of candidate warehouses, assigning each retailer to one of the selected warehouses and determining replenishment plans for the warehouses and the retailers. For the problem with the objective of minimizing the sum of warehouse operation costs, inventory holding costs at the warehouses and the retailers, and transportation costs from the CDC to warehouses as well as from warehouses to retailers, we present a non-linear mixed integer programming model and develop a heuristic algorithm based on Lagrangian relaxation and subgradient optimization methods. A series of computational experiments on randomly generated test problems shows that the heuristic algorithm gives relatively good solutions in a reasonable computation time.     

An agent-based nurse rostering system under minimal staffing conditions

Nurse rostering is a complex problem. We propose a new heuristic using a competitive agent-based negotiation that focuses on nurse preferences called competitive nurse rostering (CNR). Unlike the existing literature, CNR models each nurse's preference functions separately and separates the cost minimization and preference maximization problems. CNR produces quality nurse rosters even though it cannot leverage extra staffing. As an agent system, CNR can distribute computational requirements over several computer systems, include other solution methods at various points in of the rostering problem, and act as a real-time scheduling system. These benefits are not naturally inherent in centralized heuristic solutions.     

可化为单约束的线性规划问题

本文主要讨论可以化为单约束的多约束线性规划问题。对于这类问题,在寻求较简单解法时提出了主约束概念和判别主约束的方法,并探讨了此法在化简其它一些线性规划问题方面的应用。     

Two-stage flowshop earliness and tardiness machine scheduling involving a common due window

This paper studies a non-preemptive two-stage flowshop scheduling problem to minimize the earliness and tardiness under the environment of a common due window. The window size and the window location are considered to be given parameters. The just-in-time problem exists naturally and has many practical applications. The problem is shown to be NP-complete in the strong sense. We develop a branch and bound algorithm and a heuristic to solve the problem. We conduct the computational experiments to test the performances of the algorithms. A strong lower bound is derived for the branch and bound algorithm that can efficiently solve 15 jobs problem for about 5 minutes. The heuristic is shown to be efficient and effective, which can solve the problem of 150 jobs for about 20 seconds and provide near-optimal solution. We justify that the heuristic is an excellent solution approach for large problem instances. We also show that four special cases are either polynomial solvable or NP-complete in the ordinary sense.     

线形规划法在我国医药经销商遴选中的应用

目的 本文运用线性规划的方法对我国经销商遴选问题进行优化设计，实现在既定约束下，将利润最大化、方法线性规划法、比较静态分析，结果运用线性规划的遴选方法优于传统的单目标决策方法。     

A state space augmentation algorithm for the replenishment cycle inventory policy

In this work we propose an efficient dynamic programming approach for computing replenishment cycle policy parameters under non-stationary stochastic demand and service level constraints. The replenishment cycle policy is a popular inventory control policy typically employed for dampening planning instability. The approach proposed in this work achieves a significant computational efficiency and it can solve any relevant size instance in trivial time. Our method exploits the well known concept of state space relaxation. A filtering procedure and an augmenting procedure for the state space graph are proposed. Starting from a relaxed state space graph our method tries to remove provably suboptimal arcs and states (filtering) and then it tries to efficiently build up (augmenting) a reduced state space graph representing the original problem. Our experimental results show that the filtering procedure and the augmenting procedure often generate a small filtered state space graph, which can be easily processed using dynamic programming in order to produce a solution for the original problem.     

Scheduling jobs with values dependent on their completion times

The paper concerns two scheduling problems with job values and losses of job values (costs) dependent on job completion times. In the first problem, we consider scheduling jobs with stepwise values in parallel processor environment. In the stepwise value, there is given a number of moments at which the job value decreases and between them the job value is constant (thus, the value deteriorates over time). The maximized criterion is the total job value. We prove strong NP-hardness of a single processor case of the problem and construct a pseudo-polynomial time algorithm for a special case with fixed number of unrelated parallel processors and fixed number of common moments of job value changes. Additionally, for uniform and unrelated parallel processors we construct and experimentally test several heuristic algorithms based on the list strategy. The second problem is a single processor one with piecewise linear losses of job values (the loss increases over time). The minimized criterion is the total loss of job value. We prove strong NP-hardness of the problem and existence of a pseudo-polynomial time exact algorithm for its special case. We also construct some heuristic algorithms for this problem and verify experimentally their efficiency.     

Ship routing problem with berthing time clash avoidance constraints

We consider a ship routing problem in which multiple vessels have to perform pickups and deliveries of cargoes at various locations. The loading and unloading time of cargoes at pickup and delivery locations is significant, and at each of these locations we need to assign a time slot to each vessel to perform the loading/unloading task so as to avoid time clashes. This problem is motivated by the operations of feeder vessels and company-owned cargo terminals, where the shipping company wishes to coordinate the routing and the berthing time of its vessels. We develop a heuristic algorithm for the problem using set partitioning formulation and column generation techniques. The effectiveness of the heuristic is tested via extensive computational experiments.