直运越库物流的精确算法研究

多车辆直运越库调度问题的目标是最小化所有客户中的最晚到货时间.首先,建立了描述该问题的混合整数线性规划模型,并使用运筹优化工具ILOG CPLEX进行求解;其次,构造了基于LPT规则的启发式算法,为精确算法提供了初始可行解,并对分支定界算法进行详细的分析;最后,在数值实验部分,通过数学模型与分支定界的比较及算法性能的分析后,得出分支定界算法具有更高的效率,该分支定界算法在合理的时间内能够求解到11个供应商规模的问题.     

解复杂二次整数规划问题的新型分枝定界算法

针对二次整数规划问题的特征，本文对传统分枝定界算法做了一系列的改进，其包括用HNF算法寻求初始整数可行解、对变量进行某种先验排序以确定分枝变量的选取次序、及针对变量的特性来选取分枝方向等，给出了可用于求解中大规模复杂二次整数规划问题的改进型分枝定界算法。数值试验结果表明所给算法大大改进了传统的分枝定界算法，并有广泛的适用性。     

带有界约束非凸二次规划问题的整体优化方法

通过研究带有界约束非凸二次规划问题，给出了求解该问题的整体最优 解的分枝定界方法及其收敛性，提出了定界的紧，松驰策略，把球约束二次规划问题作为子问题来确定原问题的整体最优值下界和上界，应用分枝定界方法达到了对原问题的求解。     

考虑人员能力差异的装配生产线优化

针对具有人员能力差异的装配生产线节拍优化问题,建立数学模型,提出一种先分配工序、后分配工人的分步求解启发式方法,并分别利用双种群遗传算法和分枝定界法对其进行求解;提出构建原优化问题的上下界,并以某企业的装配生产线为实例,验证了本方法的有效性与实用性。     

面向汽车整车出厂物流的两阶段组合装箱调度优化模型与算法研究

研究组合装箱与道位分配的两阶段出厂物流的调度模型与算法,问题将考虑订单、驳运车、仓库道位资源、客户需求、配送成本等多种因素。首先将所研究问题划分为带装箱约束、方向约束和拼车约束的组合装箱子问题,和带驳运车到达时间及道位不可用时间段的道位分配问题。针对两个子问题建混合线性整数模型并分别设计了分支定界和启发式算法,实现两阶段整合求解。最后,通过数值实验和与人工调度结果的对比模型,表明了模型和算法的有效性。     

基于多重约束的飞机移动装配线作业调度优化

基于对飞机移动装配线作业多重约束的分析,建立了作业调度优化问题的整数规划模型,提出了组合优先规则WRST以及基于此规则的启发式算法.WRST综合考虑了最迟完成时间、资源以及空间稀缺度三个指标;而算法设计包括基于WRST规则的作业拓扑排序和作业资源分配两阶段.数值试验结果显示基于WRST规则的启发式算法求解质量高,求解速...     

空箱资源约束调度的列生成算法研究

研究了可重用空箱资源约束下的入厂物流车辆运输调度问题。首先对该问题进行数学描述,建立混合整数线性规划模型。鉴于问题的NP难解性,研究求解该问题的列生成方法,提出虚工件等技巧,建立适合序列依赖的可重用资源约束调度的列生成主问题模型以及基于检验数求解的子问题模型,并研究求解子问题的动态规划算法。进一步采用分支定界技巧,最终提出适合本问题求解的列生成算法。数值实验表明方法的有效性与高效性。     

分枝定界MIMO检测算法的推广及改进

将分枝定界这种优化搜索算法用在MIMO系统中,并且推广到非二进制高阶调制的情况,在基本算法的基础上提出了对信号排序和候选节点排序的改进算法.仿真结果表明,分枝定界算法是一种最大似然检测算法,提出的改进算法加快了收敛速度,降低了计算复杂度和对存储空间的要求,从而证明了改进算法的有效性.     

基于粒子群算法的半导体制造设备预维修调度

对半导体制造设备的预维修调度问题进行了研究,建立了半导体制造设备预维修调度的数学模型,分别提出了用于求解该问题的启发式方法和粒子群算法方案,阐明了两种算法方案的具体实现过程。通过对仿真实例进行计算和结果比较,表明了粒子群算法优于启发式方法,取得了不错的优化效果。     

加工时间存在双重约束的批调度模型及算法

为了提高热处理的加工效率并实现准时交货,本文根据热处理各批次加工时间受装炉量和批中最大工件尺寸双重约束的特点,分别以最小化最大完成时间和最小化最大拖期量为调度目标,构建混合整数线性规划模型Model C和Model L。根据分批数量上界设定值与Model C运算结果的关系特性,构建启发式算法HC提高Model C的运算效率。通过反例说明Model C所具有的特性并不适用于求解Model L。提出启发式算法HL求解最小化最大拖期量问题,并证明算法HL的计算复杂度。通过大量实验数据验证,结果显示两个数学模型都分别能够求得最优解,但调度规模不超过18个工件;算法HC能得到调度规模为60个工件的最优解;算法HL与最优解相比平均偏差不超过15%,调度性能明显优于其他2种典型算法。     

不确定环境下的越库调度的模型及算法

研究不确定环境下的直运入厂物流调度问题。目标函数是最小化最大完工时间。供应商和客户到配送中心的运输时间的期望值和方差已知,运输时间均服从正态分布。首先研究确定性和不确定情形下的最优解差距。然后提出适用于确定和不确定情形下的带参数启发式算法,并给出面向不确定性环境的较优启发式算法,数值实验表明该算法的有效性。     

Two-machine flow shop problem with unit-time operations and conflict graph

This paper addresses the problem of scheduling, on a two-machine flow shop, a set of unit-time operations subject to the constraints that some conflicting jobs cannot be scheduled simultaneously on different machines. In the context of our study, these conflicts are modelled by general graphs. The problem of minimising the maximum completion time (makespan) is known to be NP-hard in the strong sense. We propose a mixed-integer linear programming (MILP) model. Then, we develop a branch and bound algorithm based on new lower and upper bound procedures. We further provide a computer simulation to measure the performance of the proposed approaches. The computational results show that the branch and bound algorithm outperforms the MILP model and can solve instances of size up to 20,000 jobs.     

A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.     

Scheduling direct deliveries with time windows to minimise truck fleet size and customer waiting times

This paper tackles the operational problem of scheduling direct deliveries from a single source (e.g. a distribution centre) to multiple customers (e.g. assembly plants). The problem consists of scheduling a set of given round trips such that each trip is processed exactly once within its time window and the employed truck fleet is as small as possible. Moreover, as a secondary objective, customer waiting times should be minimal. Such planning problems arise in many industries like, for instance, the automotive industry, where just-in-time parts are often shipped via direct delivery to OEMs. We propose two different mixed-integer programming models for this problem, discuss similarities to classic routing and scheduling problems from the literature, identify a subproblem that is solvable in polynomial time and propose suitable heuristics. In a computational study, the proposed procedures are shown to perform well both on newly generated instances as well as those from the literature. We also show that minimising waiting times is an adequate measure to make schedules more robust in the face of unforeseen disturbances.     

Spread time considerations in operational fixed job scheduling

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.     

An Investigation of Branch and Bound Methods for Solving the Segregated Storage Problem

The segregated storage problem consists of determining a minimum cost distribution of products among compartments such that only one product may be stored in a given compartment. This paper explores the computational aspects of using branch and bound methods to solve this problem. Such methods were first suggested for this problem by White and Francis. A variety of approaches are tested, utilizing heuristic node selection and branching decision rules. Three heuristics are also presented which generate solutions for use as initial upper bounds for improving efficiency of the branch and bound procedure or as solutions for very large problems.     

Sequencing mixed-model assembly lines to level parts usage and minimize line length

The problem of sequencing units on a mixed-model assembly line can be viewed with several objectives in mind. Past research has focused mainly on two separate performance measures: (1) minimizing the length of the line (which is equivalent to minimizing the risk of stopping the conveyor when system variability is present and the station lengths are fixed); or (2) maintaining a rate of assembly equal to the demand rate for each model type in the production schedule. The latter is the more appropriate in a just-in-time environment. We present a bicriteria formulation of the problem that can be used to examine the tradeoffs between line length and parts usage. The resultant model takes the form of a mixed integer nonlinear program and is solved with a combination of heuristics and branch and bound. Results are reported for a wide range of problem sizes, as defined by the number of stations on the line, the number of different model types, and the total number of units to be assembled. In almost all cases, at least one of the heuristics found either the optimum or the best available solution. Computation times were quite reasonable for the heuristics, but grew exponentially for branch and bound. In general, it was only possible to verify optimality on problems with 20 units.     

基于物流能力约束的整车物流计划

基于时间竞争的敏捷供应链环境中,汽车整车物流必须按照客户订单对交货期、交货地点等的要求进行快速响应和准时配送.整车运输能力作为物流要素能力之一,由于其特殊性已成为整车物流的瓶颈,对物流绩效和供应链绩效形成重要影响.从压缩订单响应时间角度出发,在以整车运输能力为约束的条件下,提出了汽车整车物流准时配送计划问题,参照并行多机提前/拖期问题的研究方法,设计了一种制定整车物流配送计划的启发式算法,最后通过算例证明所提算法的可行性.     

Iterated beam search for the combined car sequencing and level scheduling problem

The level scheduling problem is concerned with the final stage of a multi-stage just-in-time production system so that different models of a product are evenly distributed in a discrete production sequence, thereby making the problem practically an unconstrained optimisation problem. The car sequencing problem, on the other hand, is a constraint satisfaction problem based on a number of options constricting the final assembly schedule. The combined car sequencing and level scheduling problem aims to find the optimal production schedule that evenly distributes different models over the planning horizon and satisfies all option constraints. This paper proposes a parametric iterated beam search algorithm for the combined problem that can be used either as a heuristic or as an exact optimisation method. The paper includes a computational study based on a 54-instance test bed that proves the effectiveness of the proposed algorithm.