A HEURISTIC FOR F3/bi= b/C_(max) AND ITSWORST-CASE ANALYSIS

1.IntroductionTheF3Cm..canbestatedasfOllows.Eachofthenjobs1,2,'')nistobeprocessedonthreemachinesA,B,Cinthesameorder.Giventheprocessingtimesal?hiandciofjobionmachinesA,BandC,findtheorderinwhicheachmachineshouldprocessethejobssoastominimizingthetotaltimesp…     

两阶段流水车间成组调度问题的迭代贪婪算法

针对两阶段流水车间成组调度问题，在同时考虑序列不相关准备时间和阶段间双向运输时间约束的情况下，以最小化最大完工时间为目标建立了混合整数线性规划模型，结合问题特征提出一种协同进化迭代贪婪算法.算法将工件组间排序和各工件组内工件间排序两个子问题进行统一编码，设计了不同的启发式规则产生问题的初始解，并提出一种协同导向迭代贪婪规则对两个子问题进行联合优化，进而给出了问题的三个下界以评估算法的性能.通过不同规模的数据实验和与对比算法的比较分析，验证了所提算法的高效性和稳健性.     

带外包受限批量模型的启发式遗传算法

研究了生产和外包数量受限的动态批量问题,引入虚拟生产量实现问题转换。设计了启发式遗传算法：针对01变量的编码方案;每周期虚拟生产量的最优分配方案;修正不可行解的局部启发式平移过程;修正遗传算法最好解的启发式前后向过程。进行了算子组合、交叉变异概率组合和精英策略影响试验;通过大量仿真试验,验证了所提算法的性能。     

能力受限批量问题的启发式算法与CPLEX仿真优化

能力受限批量问题多数都是NP-hard问题,解决方法之一就是构造启发式算法获取尽量接近最优解的可行解。目前多数文献通过大规模计算分析来评价启发式算法的性能,但是这种评价方式只能表明该算法针对特定实例的适应性。利用商业优化软件求解同一实例并与算法计算结果进行对比分析,可以体现算法的有效性。针对一种运输能力外包且费用时变的多产品动态经济批量问题,建立混合整数规划模型,通过约束松弛与模型分解,设计出一个基于拉格朗日松弛理论的启发式算法进行模型求解。大量随机实验计算结果以及CPLEX仿真优化结果对比分析表明,在某些实例情况下,启发式算法获取的最优值与CPLEX获取的相当,但是求解时间要明显优于CPLEX,因此选择启发式算法求解此类实例是较优的。     

A LAGRANGIAN RELAXATION APPROACH FOR SUPPLY CHAIN PLANNING WITH ORDER／SETUP COSTS AND CAPACITY CONSTRAINTS

A heuristic approach is developed for supply chain planning modeled as multi-item multi-levelcapacitated lot sizing problems. The heuristic combines Lagrangian relaxation(LR) with local search.Different from existing LR approaches that relax capacity constraints and/or inventory balanceconstraints, our approach only relaxes the technical constraints that each 0-1 setup variable must takevalue 1 if its corresponding continuous variable is positive. The relaxed problem is approximatelysolved by using the simplex algorithm for linear programming, while Lagrange multipliers are updatedby using a surrogate subgradient method that ensures the convergence of the dual problem in case ofthe approximate resolution of the relaxed problem. At each iteration, a feasible solution of the originalproblem is constructed from the solution of the relaxed problem. The feasible solution is furtherimproved by a local search that changes the values of two setup variables at each time. By taking theadvantages of a special stru     

k-冗余结构无线自组网广播算法研究

针对k-冗余连接路由算法的特点,对最优广播树的生成算法进行了研究。首先根据最优广播树的数学模型,证明了它是一个NP难题(NP-Complete)。然后针对网络拓扑的特点提出了启发式广播树生成算法。针对算法的特点,分析了算法复杂度和算法的效率。结合GlomoSim仿真平台,在无线网络环境下对算法的效率进行了仿真,将协议的性能与简单广播算法进行了比较。仿真结果表明,启发式广播算法能够减小网络开销和节点的转发次数,提高网络的传输效率。     

一类带有安装时间的单机成组排序问题

针对一类带有准备时间和安装时间的单机成组排序问题,给出了求解最优排序的多项式算法。其中每个工件都具有自己的准备时间,组和组之间具有安装时间,并且安装时间和已经加工完工件的加工时间有关。所有工件在机器上加工时,一次只能加工一个工件,工件不可中断,组内工件连续加工,组和组之间需要安装时间。对目标函数为极小化最大完工时间的单机成组排序问题,给出了求解最优排序的多项式算法。原问题不是成组问题,为此在原问题的基础上添加了工件的成组问题且组内每个工件都具有自己准备时间,其结果是依然能给出求解最优排序的多项式算法。     

单机订单接受与加工调度问题的拉格朗日松弛算法

针对不同类型订单加工切换时机器需要准备时间的实际生产情况，研究了单机订单接受与加工调度优化决策问题，旨在最大化企业净收益。鉴于研究问题的强NP难属性，设计了基于拉格朗日松弛理论的启发式算法。首先，该算法通过加入相邻订单相异性约束以提高松弛解质量；其次，应用动态规划递推公式求解拉格朗日松弛问题；最后，利用问题的优化性质并基于贪婪规则构造原问题可行解。不同规模问题的实验结果表明，该算法能在合理计算时间内得到满意的近优解。     

堆区混贝的堆场场吊调度模型与算法

为提高集装箱码头堆场场吊作业效率,研究了堆场单堆区混贝条件下的场吊调度问题.在单堆区内集装箱混贝堆放的前提下,提出了堆场场吊装卸作业时间窗约束、作业次序依赖的设备调整时间及堆场空间约束等,并在此基础上建立了整数规划模型.针对这一模型设计了改进禁忌搜索算法对问题进行求解.最后通过数值实验表明改进后的算法在对大规模问题求解时具有良好的效果,且算法效率较高.     

求解目标是最小完成时间和的同类机调度的改进算法

研究了目标函数是完成时间和的同类机调度问题。同类机调度是一种重要的平行机调度问题,而最小完成时间和目标是最常见的规则目标一种,完成时间和的同类机调度问题在相关研究领域具有非常重要的地位。首先为此问题建立数学模型,然后提出一种改进的启发式算法,并通过实验验证了算法的性能。     

有模具约束的平行机台最小拖期和调度问题

针对某电器企业的一个瓶颈工序来制定调度方案，该问题归纳为平行机台具有模具约束，目标为最小拖期和的调度问题．本文提出了如下的启发式算法：根据模具情况运用成组技术对工作成组并生成运行表：按运行表顺序对各个运行中的工作进行指派机台，设置禁忌模具集合，避免对运行的短视性；根据工作的交货期和加工时间选择适当的机台进行加工；在各个机台运用ＮＢＲ（ＮｅｔＢｅｎｅｆｉｔｏｆＲｅｌｏｃａｔｉｏｎ）算法调节顺序以减少拖期和．该算法在厂家的实际测试中，通过三个不同的实例与手工排程进行了比较，各项指标均有明显优势．     

带机器准备时间的同类机调度问题的启发式算法

研究了带机器准备时间的同类机最大完工时间调度问题, 首先证明了工件互换的四个性质, 进而提出了一种启发式算法, 此算法以LPT算法得到的序列作为初始解, 利用互换性质重复对最大完工时间最大和最大完工时间最小的两台机器上的工件进行交换, 以提高解的质量. 实验结果证明了此算法的有效性.     

多工件族无缓冲混合Flow Shop问题的模型和算法构建

旨在研究并解决一类从集装箱混合装卸作业环境中提取的多工件族无缓冲混合Flow Shop问题. 针对该问题的多工件族、无缓冲、部分专用机、与机器和顺序相关的准备时间和作业时间等特点, 构建了问题的混合整数线性规划模型. 鉴于问题的NP-hard特性, 构造型的启发式算法被构建, 核心思想是基于提出的机器库存和配额等概念, 动态构建含有三元副的调度列表, 三元副表示与其一一对应的工件在3阶混合Flow Shop中的加工轨迹. 通过仿真实验、下界分析, 发现算法能获得好的近优解和低的计算成本. 更为重要的是, 算法尤其适合解决大规模的实际问题.     

集装箱码头装卸系统集成调度的建模与优化

为提高集装箱码头作业效率,在码头集装箱卡车作业能力充足的条件下,对集装箱码头作业装卸系统集成调度问题进行了研究.针对集装箱码头装卸作业的特点,提出了装卸作业的预定义顺序约束、作业次序依赖的设备调整时间及岸桥碰撞干涉约束等,并在此基础上建立了整数规划模型.针对这一模型设计了两阶段启发式算法对问题进行求解.通过在数值实验中将结果与低界相比较,证明该算法效果良好.特别对于规模较大的问题,算法也可以进行有效的求解.     

带运输和设置时间的无等待并行流水车间调度问题研究

研究了一类从无缝钢管生产作业中提炼出的新的并行流水车间调度问题.该问题具有工件无等待、工序之间存在运输时间、设备需要调整时间等特点.这些特点使得问题变得相当复杂.建立了大规模的混合整数规划模型,通过提出的变换方法简化和降低了模型的规模.针对此模型,提出并开发了适合此问题的遗传算法.通过实验比较六种规则调度方法及遗传算法的性能.计算结果表明,六种规则调度中最好的方法是SPT,而遗传算法调度的性能优于SPT.     

Batching Scheduling in a Two-Level Supply Chain with Earliness and Tardiness Penalties

This paper studies the batch sizing scheduling problem with earliness and tardiness penalties which is closely related to a two-level supply chain problem. In the problem, there are K customer orders, where each customer order consisting of some unit length jobs has a due date. The jobs are processed in a common machine and then delivered to their customers in batches, where the size of each batch has upper and lower bounds and each batch may incur a fixed setup cost which can also be considered a fixed delivery cost. The goal is to find a schedule which minimizes the sum of the earliness and tardiness costs and the setup costs incurred by creating a new batch. The authors first present some structural properties of the optimal schedules for single-order problem with an additional assumption (a): The jobs are consecutively processed from time zero. Based on these properties, the authors give a polynomial-time algorithm for single-order problem with Assumption (a). Then the authors give dynamic programming algorithms for some special cases of multiple-order problem with Assumption (a). At last, the authors present some structural properties of the optimal schedules for single-order problem without Assumption (a) and give a polynomial-time algorithm for it.     

超启发式DE算法求解零等待发酵工艺调度

为解决具备间歇过程特点的零等待发酵工艺调度过程中易变质的难点,提出了一种超启发式差分算法,并将最小化最大完工时间设置为优化目标。此算法分为2层,高层为改进的自适应差分进化算法,来对低层的启发式操作进行选择排序。而低层组合排序成了新的算法对问题域进行操作,加入模拟退火算法避免陷入局部最优。所提出的方法具有学习的机制,对不同问题具有较强的泛化能力。通过测试算例和实际生产进行算法的比较和求解验证了此算法的有效性,结果表明所提出的算法比传统的启发式算法性能更优。     

求解多目标作业排序问题的遗传算法

利用联合进化遗传算法 ( CEGA)建立了求解多目标排序问题的一般框架 ,采用目标权衡分析诱导出决策人的偏好关系 ,并将其引入求解过程 ,以确定满意排序 ,在搜索寻优过程中 ,将启发式与遗传算法相结合 ,以提高搜索效率 .最后 ,利用该算法框架求解了一个含调整时间的一般 Job Shop排序问题 ,以表明算法的有效性.     

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究3台机器调整时间可分离的无等待F1ow Shop排序问题，目标函数为极小化折扣加权总完工时间。对某些特殊情况，给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待F1ow Shop排序问题的分派规则。     

基于蚁群优化的置换流水车间调度算法

针对置换流水车间调度问题,提出了一种基于蚁群优化的调度算法.该算法的要点是将NEH启发式算法和蚁群优化结合起来:首先,将蚁群优化中的能见度定义为NEH中所用的工作加工时间之和.其次,对于部分解采用了NEH中的步骤2和步骤3进行局部调整.最后,对构造出的解做插入型局部搜索.用所提算法对置换流水车间调度问题的基准问题进行了测试,测试结果表明提出算法的有效性.