Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

考虑人车混采的道路信息采集的路径规划研究

本文考虑了道路信息外业采集的任务要求,人车混采的采集方式以及路网特性等方面,为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型;提出了分阶段的转化算法,将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCARP问题是一种NP-hard问题,精确求解算法无法在合理时间内得到问题的最优解,因此本文设计了求解TCARP问题的两种快速启发式算法TPS和TUH及其随机化版本;考虑到实际采集问题的大规模特性,在两种快速启发式算法的基础上构造GRASP-PA寻优算法。最后分别结合不同规模的基准算例和实际采集算例证明了本文所构造的算法的有效性。     

Hierarchical Multi‐skill Resource Assignment in the Telecommunications Industry

We formulate a discrete time Markov decision process for a resource assignment problem for multi‐skilled resources with a hierarchical skill structure to minimize the average penalty and waiting costs for jobs with different waiting costs and uncertain service times. In contrast to most queueing models, our application leads to service times that are known before the job is actually served but only after it is accepted and assigned to a server. We formulate the corresponding Markov decision process, which is intractable for problems of realistic size due to the curse of dimensionality. Using an affine approximation of the bias function, we develop a simple linear program that yields a lower bound for the minimum average costs. We suggest how the solution of the linear program can be used in a simple heuristic and illustrate its performance in numerical examples and a case study.     

Multimodal hub location and hub network design

Through observations from real life hub networks, we introduce the multimodal hub location and hub network design problem. We approach the hub location problem from a network design perspective. In addition to the location and allocation decisions, we also study the decision on how the hub networks with different possible transportation modes must be designed. In this multimodal hub location and hub network design problem, we jointly consider transportation costs and travel times, which are studied separately in most hub location problems presented in the literature. We allow different transportation modes between hubs and different types of service time promises between origin–destination pairs while designing the hub network in the multimodal problem. We first propose a linear mixed integer programming model for this problem and then derive variants of the problem that might arise in certain applications. The models are enhanced via a set of effective valid inequalities and an efficient heuristic is developed. Computational analyses are presented on the various instances from the Turkish network and CAB data set.     

TECHNOLOGICAL PROGRESS AND TECHNOLOGY ACQUISITION: STRATEGIC DECISION UNDER UNCERTAINTY

We develop a stochastic programming model to aid manufacturing firms in making strategic decisions in technology acquisition. The proposed model maximizes the firm's expected profit under the condition of the uncertainty in technological progress and development. To solve this large‐scale problem, we decompose future uncertainties through scenarios and then develop an algorithm to solve the resulting non‐linear subproblems efficiently. Finally, we develop a heuristic to eliminate the infeasibility in the master problem and obtain best solutions. Numerical results show that our heuristic solutions are very close to the optimal solutions and meaningful insights are derived.     

Integrated Procurement Planning in Multi‐division Firms

For large multi‐division firms, coordinating procurement policies across multiple divisions to leverage volume discounts from suppliers based on firm‐wide purchasing power can yield millions of dollars of savings in procurement costs. Coordinated procurement entails deciding which suppliers to use to meet each division's purchasing needs and sourcing preferences so as to minimize overall purchasing, logistics, and operational costs. Motivated by this tactical procurement planning problem facing a large industrial products manufacturer, we propose an integrated optimization model that simultaneously considers both firm‐wide volume discounts and divisional ordering and inventory costs. To effectively solve this large‐scale integer program, we develop and apply a tailored solution approach that exploits the problem structure to generate tight bounds. We identify several classes of valid inequalities to strengthen the linear programming relaxation, establish polyhedral properties of these inequalities, and develop both a cutting‐plane method and a sequential rounding heuristic procedure. Extensive computational tests for realistic problems demonstrate that our integrated sourcing model and solution method are effective and can provide significant economic benefits. The integrated approach yields average savings of 7.5% in total procurement costs compared to autonomous divisional policies, and our algorithm generates near‐optimal solutions (within 0.75% of optimality) within reasonable computational time.     

公交系统随机平衡网络设计模型及求解算法

本文根据公交网络的具体特点,对公交网络进行了系统的描述,提出一个双层规划模型来描述随机平衡公交网络设计问题。在双层规划模型中,上层模型为一个标准的公交网络设计模型,下层模型是一个公交网络随机平衡配流模型。针对所提出的模型,设计了基于灵敏度分析的求解算法。最后,给出一个简单算例加以证明。     

具有遗憾值约束的鲁棒供应链网络设计模型研究

考虑不确定性环境,研究战略层次的供应链网络鲁棒设计问题,目标是设计参数发生摄动时,供应链性能能够保持稳健性。基于鲁棒解的定义,建立从上游供应商选择到下游设施选址-需求分配的供应链网络设计鲁棒优化模型;提出确定遗憾值限定系数上限和下限的方法,允许决策者调节鲁棒水平,选择多种供应链网络结构;通过模型分解与协调,设计了供应链节点配置的禁忌搜索算法。算例的计算结果表明了禁忌搜索算法具有良好的收敛特性,以及在处理大规模问题上的优越性;同时也反映了利用鲁棒优化模型进行供应链网络设计,可以有效规避投资风险。     

An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks

We consider the problems of minimum-cost design and augmentation of directed network clusters that have diameter 2 and maintain the same diameter after the deletion of up to R elements (nodes or arcs) anywhere in the cluster. The property of a network to maintain not only the overall connectivity, but also the same diameter after the deletion of multiple nodes/arcs is referred to as strong attack tolerance. This paper presents the proof of NP-completeness of the decision version of the problem, derives tight theoretical bounds, as well as develops a heuristic algorithm for the considered problems, which are extremely challenging to solve to optimality even for small networks. Computational experiments suggest that the proposed heuristic algorithm does identify high-quality near-optimal solutions; moreover, in the special case of undirected networks with identical arc construction costs, the algorithm provably produces an exact optimal solution to strongly attack-tolerant two-hop network design problem, regardless of the network size.     

基于双层规划的供应链二级分销网络优化设计模型

从供应链集成的角度出发,利用双层规划模型描述了二级分销网络优化问题,充分考虑了网络决策部门及客户双方的自身及共同利益。同时设计了启发式求解算法,最后用一简单实例验证了模型及其算法的有效性。     

Optimal solutions versus ‘good’ solutions: An analysis of heuristic decision making

The portion of business problems which lend themselves to solution by existing optimization techniques are a minor subset of the business problems which can be defined and attacked by logical devices. Heuristics simplify the environment of the decision maker by permitting him to make decisions quickly without considering the innumerable ways that each decision could be made. This paper compares the heuristic programming approach to more traditional operations research techniques of decision making.     

Planning a sustainable reverse logistics system: Balancing costs with environmental and social concerns

The present work aims to support tactical and operational planning decisions of reverse logistics systems while considering economic, environmental and social objectives. In the literature, when addressing such systems economic aspects have been often used, while environmental concerns have emerged only recently. The social component is the one less studied and rarely the combination of the three concerns has been analyzed. This work considers the three objectives and was motivated by the challenge of supporting decision makers when managing a real case study of a recyclable waste collection system, where strategic decisions on the number and location of depots, vehicles and containers were taken beforehand. Tactical and operational decisions are studied involving the establishment of service areas for each depot and the definition and scheduling of collection routes for each vehicle. Such decisions should represent a compromise solution between the three objectives translating a sustainable reverse logistics plan. The problem is modeled as a multi-objective, multi-depot periodic vehicle routing problem with inter-depot routes. A mathematical formulation and a solution approach are proposed. An approximation to the Pareto front is obtained for the case study and the trade-offs between the objectives are discussed. A balanced solution is proposed.     

On greedy and strategic evaders in sequential interdiction settings with incomplete information

We consider a class of sequential network interdiction problem settings where the interdictor has incomplete initial information about the network while the evader has complete knowledge of the network including its structure and arc costs. In each decision epoch, the interdictor can block (for the duration of the epoch) at most k arcs known to him/her. By observing the evader’s actions, the interdictor learns about the network structure and costs and thus, can adjust his/her actions in subsequent decision epochs. It is known from the literature that if the evader is greedy (i.e., the shortest available path is used in each decision epochs), then under some assumptions the greedy interdiction policies that block k-most vital arcs in each epoch are efficient and have a finite regret. In this paper, we consider the evader’s perspective and explore deterministic “strategic” evasion policies under the assumption that the interdictor is greedy. We first study the theoretical computational complexity of the evader’s problem. Then we derive basic constructive properties of optimal evasion policies for two decision epochs when the interdictor has no initial information about the network structure. These properties are then exploited for the design of a heuristic algorithm for a strategic evader in a general setting with an arbitrary time horizon and any initial information available to the interdictor. Our computational experiments demonstrate that the proposed heuristic outperforms the greedy evasion policy on several classes of synthetic network instances under either perfect or noisy information feedback. Finally, some interesting insights from our theoretical and computational results conclude the paper.     

Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs

Disassembling complex products is formally approached via network representation and subsequent mathematical modeling, aimed at selecting a good or optimum sequence of disassembly operations. This is done via heuristics, metaheuristics or mathematical programming. In contrast with heuristics and metaheuristics, which select a near-optimum solution, mathematical programming guarantees the selection of the global optimum. This problem is relatively simple if the disassembly costs can be assumed sequence independent. In practice, however, sequence dependent disassembly costs are frequently encountered, which causes NP-completeness of the problem. Although methods, e.g., based on the two-commodity network flow approach, are available to solve this constrained asymmetric Traveling Salesperson problem rigorously, this requires the introduction of integer variables. In this paper, a modification of the two-commodity network flow approach is proposed, which reduces the number of integer variables. This is applied to product structures that can be represented by a disassembly precedence graph. It is demonstrated that use of integer variables is completely avoided by iteratively solving a binary integer linear programming problem. This appears to be more efficient than solving the corresponding integer linear programming problem. It is demonstrated, on the basis of some cases, that this method might provide the exact solution of problems with increased complexity compared to those discussed so far in the literature. This appears particularly useful for evaluating heuristic and metaheuristic approaches.     

个体客户全生命周期价值的模型和实证研究

从企业的角度出发把隐马尔可夫与动态规划技术有效地结合起来,对任意单个客户的终生价值的量化、决策以及优化进行了探讨和分析,提出了个体客户全生命周期价值动态模型,并对所提模型进行了验证。该模型能以通过观察到的客户购买决策序列作为动态最优化问题的解来进行参数评估,而且还能以用所产生的客户状态序列对客户进行动态的评价和分类,判断客户与企业所处关系阶段,从而为企业进行一对一的动态客户关系管理提供了一种定量的方法,并为公司实施最优的营销策略打下基础。     

SIMULTANEOUS BATCHING AND SCHEDULING FOR CHEMICAL PROCESSING WITH EARLINESS AND TARDINESS PENALTIES

We consider the problem of determining the allocation of demand from different customer orders to production batches and the schedule of resulting batches to minimize the total weighted earliness and tardiness penalties in context of batch chemical processing. The problem is formulated as a mixed-integer nonlinear programming model. An iterative heuristic procedure that makes use of the network nature of the problem formulation is presented to approximate an optimal solution. An algorithm polynomial in the number of batches to produce is also presented that optimally solves the problem under special cost structures.     

一种策略层项目计划的双目标优化方法

针对产品开发项目管理的实际情况,对策略层计划优化方法进行研究。以工作包的工作量估算为基础,以资源投入水平和工期最小化为目标,考虑各种约束条件,提出一种策略层项目计划问题的混合整数规划问题模型。以非支配遗传算法NSGA-II为基础框架,设计了一种改进的双目标遗传算法。该算法针对问题的特点,提出了基于资源平滑的解码算法。参考NSGA-III的关键特征,对拥挤密度计算方法进行改进。通过企业实际项目案例,验证了算法的性能和所提出的策略层项目计划方法的有效性。     

A SIMULATION AND STATISTICAL ANALYSIS OF STOCHASTIC VEHICLE ROUTING WITH TIMING CONSTRAINTS

This paper examines a generalization of the vehicle-dispatch problem in which time constraints as well as stochastic demand and travel times are considered. The objective is to minimize total travel time subject to vehicle load capacities and sequencing restrictions, meaning that certain points may be serviced only in specified time intervals. Intra-city travel times are estimated via multiple regression, and an effective heuristic is tested on single-estimate travel times. A GPSS simulation is used to evaluate the heuristic on stochastic travel times and also to examine the effects of other decision variables such as route configuration. Computational experience with an actual refuse collection problem involving 163 points per day is reported.     

求解非线性二层规划问题的模拟植物生长算法

本文以植物向光性生长理论为启发式准则,提出了一种求解非线性二层规划问题的智能优化算法。在该算法中,将二层规划上层解空间和下层反应集分别作为植物的两个生长环境,建立以生长规则为基础的植物系统演绎方式和以植物向光性理论为基础的概率生长模型,两者结合所形成的优化模式,实现了模拟植物从初始状态到完整形式的终态(没有新的树枝生长),从而得到二层规划问题的解。该方法具有搜索精度较高,求解稳定性较强的特点,通过与国外学者在非线性二层规划实际测试问题的最优值进行精度比较,表明模拟植物生长算法是有效可行的。