集装箱码头岸吊作业调度建模及调度策略研究

岸吊作业调度对集装箱码头整体运营效率具有重要影响.综合考虑岸吊实际作业中的特有约束,包括预定义顺序约束、依赖于作业次序的设备调整时间、岸吊干涉约束,建立岸吊作业调度问题的混合整数规划模型.针对混合装卸模式,使用启发式算法生成预定义作业顺序,在此基础上采用基于连续贝作业策略的启发式算法对问题进行求解.数据实验结果显示基于SPT规则和连续贝作业的启发式算法能有效利用混合装卸带来的时间节省,减少设备调整时间,对实际岸吊作业调度具有指导意义.     

集成启发式规则的混合整数规划调度模型

针对生产调度优化问题,提出了一种集成启发式规则的混合整数规划调度模型。在分析启发式规则逻辑关系的基础上,用布尔逻辑变量表达启发式规则建立了启发式规则的基本逻辑表达式及其等价代数表达式,基于基本表达式给出了启发式规则的数学表达。将启发式规则的代数表达式与混合整数规划相结合,实现了启发式规则的集成。集成启发式规则的混合整数规划调度模型在结合启发式规则的基础上进行数学优化,克服了混合整数规划难以直接利用经验规则和基于规则的调度优化性难以保证的不足。最后以某炼油过程生产调度为例说明了模型的有效性。     

交货量不确定下装备制造企业绿色供应商选择

基于绿色供应链理念,针对交货数量不确定条件下装备制造企业的绿色供应商选择与订货量分配问题,以采购成本、环境效益及产品拖期程度为准则,构建了考虑生产物料齐套要求和最小加工批量约束的随机整数规划模型;借助引入的二进制变量,将模糊的随机整数规划模型转化为清晰的多目标混合整数规划模型;进而结合缩小求解空间的思想,运用两阶段启发式算法对所建模型进行求解。算例验证结果表明,将随机整数规划模型应用于装备制造业绿色供应商选择具有较强的可行性和有效性。     

考虑作业效率差异的同类岸桥作业调度优化

针对集装箱港口岸桥调度过程中,岸桥具有作业效率差异的特点,将其视为同类平行机调度问题,同时结合岸桥作业不可相互穿越与安全距离等特有约束,建立了更加符合实际的岸桥作业调度混合整数规划模型,其优化目标是最小化装卸作业的最大完工时间。针对问题的NP-hard特性,设计了求解模型的遗传算法,对算法搜索空间进行了讨论,并推导了问题的下界。最后,通过实验算例验证了模型与算法的有效性。     

模糊环境下再制造系统批量调度研究

针对再制造系统多种不确定因素,包括回收质量、准备时间、加工时间等,研究面向再制造系统的批量调度问题.考虑回收产品存在质量差异的情况,将回收品划分为几种质量不同的工件组类型,各工件组内所有工件的准备时间和加工时间相同,为了减小准备时间和子系统切换时间,将同一工件组内的工件分批量进行调度处理.在满足交货期、加工次序和机器有限等约束条件下,以加权完工时问最小化为目标,建立了模糊环境下的混合整数规划调度模型.该问题包含了工件分批次和调度顺序两个子问题,使用遗传算法进行求解,结合实际算例得出调度策略,验证了该模型在处理再制造生产调度问题上的有效性,并进一步分析了不同批量大小对再制造调度结果的影响.     

基于CPM的多模式资源约束项目调度建模与复杂度分析

为有效降低多模式资源约束项目调度模型的复杂度和解空间,构建3类混合整数线性规划模型。运用紧上界T_TUB缩减时间序列T的上界和关键路径法缩减各项活动结束时间的上下界,以降低模型复杂度和解空间。为验证改进模型的有效性,从MRCPSP标杆案例库中选取1 106组规模不等的算例进行求解。结果表明,基于CPM的多模式资源约束项目调度模型解空间更小;决策变量同比缩小3～65倍,约束数同比缩小1～4倍;平均求解时间同比减少53%～112%,求解性能显著优于其他模型。为验证紧上界T_TUB的参数α性能,1106组算例结果表明,α越接近1,模型的复杂度越低,解空间越小。但随着算例规模增加,算例可行解探寻难度增加。因此,对大规模算例,α值应适当放宽。     

基于“两步法”的飞行冲突解脱问题求解策略

本文针对混合整数规划方法求解飞行冲突解脱较慢的问题,提出一种分步求解方法,以此来提升求解效率。该方法在确保解决冲突问题的同时,实现求解效率和解脱成本的优化。具体包括:使用混合整数线性规划方法在角度变量离散化模型中求解得到一个较好的可行解,将此可行解作为非线性模型的初值,再使用非线性规划方法进一步求解。实验结果表明,针对飞行冲突解脱问题,使用混合整数规划和非线性规划的"两步法"求解策略切实可行,实验效果良好。     

露天矿生产的车辆安排

本文以总运量最小为目标建立整数规划模型，求解中用连续松弛把该问题转化为线性规划模型，使解题难度降低。在满足约束条件的情况，使总运量增加最小的前提下，通过变量的取整改进，使逐渐逼近最优解，本文采用装箱问题来解决此问题，即车辆的调度。模型二在模型一的基础上。对矿石产量最大，总产量最大，总运量最小按优先级高低进行排序，运用目标规划方法建立模型，然后对目标规划进行线性转换，利用Lindo软件求解。     

结合车辆日检的混凝土罐车调度问题研究

结合车辆日检因素建立基于网络流模型的混凝土罐车调度问题混合整数规划模型,并提出一种结合启发式规则和车辆流冲突选择策略的遗传算法对问题优化求解。结果表明,所提出的算法可以有效地获取更优的罐车调度计划,节省企业成本、提高效益,同时可为混凝土企业的车辆购买或租用计划提供有益的指导。     

可回收垃圾库存管理和车辆调度联合优化研究

研究了“两网融合”下社区可回收物回收清运系统中的回收点库存管理和清运车辆联合调度优化问题。以回收物流失和运输成本最小化为目标，建立了混合整数规划模型。设计了内外层嵌套优化算法进行模型求解。外层使用遗传算法来决策回收点库存管理清运线，内层设计了启发式算法，针对每周期清运计划规划车辆路径，从而获得外层算法所需要的适应度值，内外层算法交替迭代，从而得到合理的清运线和路径规划决策。基于实际案例和数据，设计了多种规模算例进行对比验证，证明了所提算法性能优于Gurobi。与现行回收策略相比，所提算法最高能减少48%以上的回收成本，有利于“两网融合”回收系统的长期高效运行。     

Multi-objective mixed integer programming and an application in a pharmaceutical supply chain

Multi-objective integer linear and/or mixed integer linear programming (MOILP/MOMILP) are very useful for many areas of application as any model that incorporates discrete phenomena requires the consideration of integer variables. However, the research on the methods for the general multi-objective integer/mixed integer model has been scant when compared to multi-objective linear programming with continuous variables. In this paper, an MOMILP is proposed, which integrates various conflicting objectives. We give importance to the imprecise nature of some of the critical factors used in the modelling that can influence the effectiveness of the model. The uncertainty and the hesitation arising from estimating such imprecise parameters are represented by intuitionistic fuzzy numbers. The MOMILP model with intuitionistic fuzzy parameters is first converted into a crisp MOMILP model, using appropriate defuzzification strategies. Thereafter, the MOMILP is transformed into a single objective problem to yield a compromise solution with an acceptable degree of satisfaction, using suitable scalarisation techniques such as the gamma-connective technique and the minimum bounded sum operator technique. The proposed solution method is applied to several test problems and a multi-objective pharmaceutical supply chain management model with self generated random data.     

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.     

Scheduling the operations of a double-load crane in slab yards

This paper studies a double-load crane scheduling problem (DLCSP) in steel slab yards. A slab yard stores slabs in stacks. To prepare for use in production, some slabs need to be moved from one place to another. These movement tasks are performed by a double-load crane which can hold up to two slabs simultaneously. Given a set of tasks and possibly precedence relationships among them, the scheduling problem is to allocate the tasks to double-load operations and determine the schedule for the crane to perform the tasks so as to minimise the makespan. The problem is first formulated as a mixed integer linear programming (MILP) model with variables representing the order of tasks. Based on properties of the problem, it is then reformulated from a crane operation perspective. Computational experiments are carried out on practical data collected from a steel company. The results show that both models can solve practical sized problems optimally, with the second model being more efficient.     

OPTIMIZATION OF STIFFENED LAMINATED COMPOSITE PLATES WITH FREQUENCY CONSTRAINTS

The problem considered in this paper concerns the maximization of frequencies of stiffened laminated composite plates subject to frequency separation constraints and an upper bound on weight. The number of plies of given fiber orientations and the stiffener areas form the two sets of design variables and the problem belongs to the class of nonlinear mixed integer programming ( NMIP) Several efficiency measures are adopted to reduce the computational cost of the optimization process. As a result of these efficiency measures, structural optimization of laminated composite plates using nonlinear mixed integer programming becomes a viable alternative to using the conventional practice of obtaining designs by an ad hoc rounding off of the continuous designs.     

Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines

This paper focuses on simultaneous optimisation of production planning and scheduling problem over a time period for synchronous assembly lines. Differing from traditional top-down approaches, a mixed integer programming model which jointly considers production planning and detailed scheduling constraints is formulated, and a Lagrangian relaxation method is developed for the proposed model, whereby the integrated problem is decomposed into planning, batch sequencing, tardiness and earliness sub-problems. The scheduling sub-problem is modelled as a time-dependent travelling salesman problem, which is solved using a dynasearch algorithm. A proposition of Lagrangian multipliers is established to accelerate the convergence speed of the proposed algorithm. The average direction strategy is employed to solve the Lagrangian dual problem. Test results demonstrate that the proposed model and algorithm are effective and efficient.     

Steel-making process scheduling using Lagrangian relaxation

The steel-making process, including steel-making and continuous casting, is usually the bottleneck in iron and steel production. Effective scheduling of this process is thus critical to improve productivity of the entire production system. Unlike the production scheduling in the machinery industry, steel-making process scheduling is characterized by the following features: job grouping and precedence constraints, set-up and removal times on the machines, and high job waiting costs. These features add extra difficulties to the scheduling problem. The objective is to ensure continuity of the production process and just-in-time delivery of final products. In this paper, a novel integer programming formulation with a 'separable' structure is constructed considering all the above-mentioned features. A solution methodology is developed combining Lagrangian relaxation, dynamic programming and heuristics. After relaxing two sets of 'coupling constraints', the relaxed problem is decomposed into smaller subproblems, each involving one job only. These subproblems are solved efficiently by using dynamic programming at the low level while the Lagrangian multipliers are iteratively updated at the high level by using a subgradient method. At the termination of such iterations, a two-stage heuristic is then used to adjust subproblem solutions to obtain a feasible schedule. A numerical experiment demonstrates that the method generates high quality schedules in a timely fashion.     

MIP-based fix-and-optimise algorithms for the parallel machine capacitated lot-sizing and scheduling problem

This paper examines the capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such a problem frequently arises in the semiconductor manufacturing industry by which this paper is motivated. A mixed integer programming (MIP) model is constructed for the problem. Two MIP-based fix-and-optimise algorithms are proposed in which the binary decision variables associated with the assignment of machines are first fixed using the randomised least flexible machine (RLFM) rule and the rest of the decision variables are settled by an MIP solver. Extensive experiments show that the proposed algorithms outperform the state-of-the-art MIP-based fix-and-optimise algorithms in the literature, especially for instances with high machine flexibility and high demand variation.     

An interval-parameter two-stage stochastic integer programming model for environmental systems planning under uncertainty

An interval-parameter two-stage stochastic mixed integer programming (ITMILP) technique is developed for waste management under uncertainty. It is a hybrid of inexact two-stage stochastic programming and mixed integer linear programming methods. The ITMILP method can directly handle uncertainties expressed not only as probability density functions but also as discrete intervals. It can be used to analyse various policy scenarios that are associated with different levels of economic penalties when the promised policy targets are violated. More importantly, it can facilitate dynamic analysis of decisions on capacity expansion planning within a multi-region, multi-facility, multi-period, and multi-option context. The results will help to generate a range of decision alternatives under various system conditions, and thus offer insight into the trade-offs between environmental and economic objectives. The ITMILP method is applied to planning facility expansion and waste flow allocation within a waste management system. The results indicate that reasonable solutions have been generated for both binary and continuous variables. The binary-variable solutions represent the decisions of facility expansion, while the continuous-variable solutions are related to decisions on waste flow allocation.     

Cutting Plane and Branch and Bound for Solving a Class of Scheduling Problems

Two general purpose integer programming algorithms, one a fractional cutting-plane algorithm and the other a branch-and-bound algorithm, were investigated. The cutting-plane algorithm easily solves an important class of integer problems, a class of scheduling problems for the assigning of personnel to work shifts over a fixed period of time. Scheduling problems were constructed with 14 to 189 integer variables and with 14 to 21 constraints. The general branch-and-bound search was not effective on this class of scheduling problems, but it was effective on the classical test problems found in the literature of integer programming, many of which were not handled by the cutting-plane algorithm.     

Hybrid approach for the integrated scheduling of production and transport processes along supply chains

The rise of new information and communication technologies leads to enhanced information transparency in supply chains. In order to utilise the resulting potentials, novel scheduling approaches that are capable of processing large amounts of data and coping with dynamic disturbances of manufacturing and transport stages have to be developed. For this purpose, the paper at hand proposes a hybrid approach for the integrated scheduling of production and transport processes along supply chains. The procedure combines mixed integer linear programming, discrete event simulation and a genetic algorithm. Obtained results show a significant reduction in the number of late orders, substantiating that proper scheduling approaches combined with information visibility allow for operational improvements in manufacturing supply chains.