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

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

多资源作业车间的混合自适应GA优化调度

针对多资源约束的车间调度问题,将启发式算法和自适应GA优化方法结合起来,提出了混合自适应GA方法,建立了多资源约束的车间优化调度模型.根据启发式调度算法中优先规则对调度目标的影响,设计了新的编码规则.采用正弦函数作为自适应因子,使得交叉概率和变异概率随群体的适应度自动改变,提高了运算的效率,克服了启发式算法和普通GA的缺陷.通过实例仿真并与其他算法比较结果表明,混合自适应GA算法可以很好的解决作业车间在机床、刀具等多种生产资源约束下的优化调度,并在评价指标上较其他算法更优.     

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

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

造船生产钢板供应匹配问题优化模型研究

针对造船生产中的钢板供应问题,研究了如何使用库存钢板进行匹配替代的模型及算法。在分析供应匹配规则和要求的基础上,建立了以余料浪费最小为目标的钢板供应匹配优化模型。将该模型归结为一种特殊的广义任务指派问题模型,对此提出一种遗传算法与匈牙利算法结合的混合启发式算法。实际算例分析表明:与传统人工作业相比,该模型可大幅提高匹配效果和钢板利用率。     

越库物流调度问题及其近似与精确算法

在提出问题基础上,建立了基于在制品优化目标的调度模型;根据模型的不同调度特征,给出问题求解的启发式近似算法,并对算法的计算复杂性进行分析,提出问题精确求解的分枝定界算法;通过数值实验验证所给出算法的有效性.表明:分枝定界算法可以有效求解多达40个货物品种的准时制配送问题;启发式算法也具有较高的计算精度,为实际越库物流管理奠定算法基础.     

研发型企业多项目人力资源调度研究——基于蚁群优化的超启发式算法

现阶段,研发型企业的项目处于多项目环境下,为了解决多项目并行时人力资源争夺问题,本文针对该类企业多项目管理中人力资源调度进行优化研究,以考虑项目延期惩罚成本的最小总成本为目标函数,将现实问题抽象建模。基于国内外的研究提出了一种超启发式算法进行求解,该算法将人力资源调度问题分为项目活动分配和人员选择项目活动两个部分,采用蚁群优化作为高层启发式策略搜索低层启发式规则,再进一步根据规则解构造出可行解。最后本研究设计多组仿真实验与启发式规则进行对比,结果表明该算法有较好的搜索性能,为人力资源的调度问题提供了新的解决方案。     

考虑预防性维护的批处理机调度问题研究

研究了考虑预防性维护的单机批处理的组批和调度联合优化问题。建立了以最小完工时间作为目标函数的组批、批调度与柔性预防性维护联合优化的数学模型,并从数学上证明了此问题可通过先组批再调度的两阶段方法求解。在此基础上,首先提出了一种考虑预防性维护的组批规则,并从数学上证明了该规则对优化目标的有效性。然后,通过改进已有的启发式算法解决批调度和预防性维护联合优化问题。最后,通过仿真试验验证了提出的组批规则和改进的启发式算法的两阶段方法是有效的。     

改进的单亲遗传算法求解倒垛问题

针对仓储物流中常常遇到的倒垛问题进行了分析,建立了0-1非线性整数规划模型,根据模型特点将其归结为具有问题特征的可扩展广义指派问题,该问题具有NP-难的性质,因此获得较大规模最优解是不可能的或是非常困难的.为了求解此问题,本文设计了一种特殊序号编码方式的单亲遗传算法,同时为了保持群体多样性,嵌入了启发式规则进行扰动.仿真算例表明改进后的算法较传统的遗传算法更具有效性.     

一种基于蜜蜂进化选择算子的布局遗传算法

三维矩形布局问题属于NP难问题,对于三维矩形布局问题的求解大多依赖于各种启发式算法.该文以布局物体体积递减为定序规则,结合布局物体在布局空间中的几何可行域,以吸引子法为定位规则,利用蜜蜂进化型遗传算法优化吸引子函数中的参数来求解三维矩形布局问题（BEGA）,得到新型布局遗传算法.最后对不同的算例进行了计算,并与以标准比例选择作为选择算子的传统布局遗传算法（SPGA）等对比证明了该算法的有效性.     

A heuristic approach for balancing mixed-model assembly line of type I using genetic algorithm

The mixed model assembly line is becoming more important than the traditional single model due to the increased demand for higher productivity. In this paper, a set of procedures for mixed-model assembly line balancing problems (MALBP) is proposed to make it efficiently balance. The proposed procedure based on the meta heuristics genetic algorithm can perform improved and efficient allocation of tasks to workstations for a pre-specified production rate and address some particular features, which are very common in a real world mixed model assembly lines (e.g. use of parallel workstations, zoning constraints, resource limitation). The main focus of this study is to study and modify the existing genetic algorithm framework. Here a heuristic is proposed to reassign the tasks after crossover that violates the constraints. The new method minimises the total number of workstation with higher efficiency and is suitable for both small and large scale problems. The method is then applied to solve a case of a plastic bag manufacturing company where the minimum number of workstations is found performing more efficiently.     

Heuristic procedures for solving the general assembly line balancing problem with setups

The general assembly line balancing problem with setups (GALBPS) was recently defined in the literature. It adds sequence-dependent setup time considerations to the classical simple assembly line balancing problem (SALBP) as follows: whenever a task is assigned next to another at the same workstation, a setup time must be added to compute the global workstation time, thereby providing the task sequence inside each workstation. This paper proposes heuristic procedures, based on priority rules, for solving GALBPS, many of which are an improvement upon heuristic procedures published to date.     

求解考虑顺序相关调整时间的双边装配线平衡问题的变邻域搜索算法

为有效解决带有顺序相关调整时间的双边装配线平衡问题,提出了一种简单高效的变邻域搜索算法。该算法通过将优先关系约束融入到交换、插入、交叉、变异等算子中,分别得到4个不同的邻域结构来保证搜索过程中解的可行性,避免过多重复邻域解的生成。4个邻域结构的搜索空间依次变大,以增强算法搜索能力。同时,结合装配线的特点,提出基于作业序列的编码和解码方式,在解码过程中,优先选择空闲时间较多的边,引入启发式目标加快算法收敛。分配结束后,对装配线末端的工作站组进行局部调整。通过将该算法先后用于求解无/有顺序相关调整时间的双边装配线平衡第一类问题,并与已有的算法进行对比,验证了所提的变邻域搜索算法的优越性和有效性。     

Stochastic assembly line balancing using beam search

This paper presents a beam search-based method for the stochastic assembly line balancing problem in U-lines. The proposed method minimizes total expected cost comprised of total labour cost and total expected incompletion cost. A beam search is an approximate branch and bound method that operates on a search tree. Even though beam search has been used in various problem domains, this is the first application to the assembly line balancing problem. The performance of the proposed method is measured on various test problems. The results of the computational experiments indicate that the average performance of the proposed method is better than the best-known heuristic in the literature for the traditional straight-line problem. Since the proposed method is the first heuristic for the stochastic U-type problem with the total expected cost criterion, we only report its results on the benchmark problems. Future research directions and the related bibliography are also provided in the paper.     

Balancing two-sided assembly lines with sequence-dependent setup times

Two-sided assembly lines are often designed to produce large-sized products, such as automobiles, trucks and buses. In this type of production line, both left-side and right-side of the line are used in parallel. In all studies on two-sided assembly lines, sequence-dependent setup times have not yet been considered. However, in real life applications, setups may exist between tasks. Performing a task directly before another task may influence the latter task inside the same station, because a setup for performing the latter task may be required. Furthermore, if a task is assigned to a station as the last one, then it may cause a setup for performing the first task assigned to that station since the tasks are performed cyclically. In this paper, the problem of balancing two-sided assembly lines with setups (TALBPS) is considered. A mixed integer program (MIP) is proposed to model and solve the problem. The proposed MIP minimises the number of mated-stations (i.e., the line length) as the primary objective and it minimises the number of stations (i.e., the number of operators) as a secondary objective for a given cycle time. A heuristic approach (2-COMSOAL/S) for especially solving large-size problems based on COMSOAL (computer method of sequencing operations for assembly lines) method is also presented. An illustrative example problem is solved using 2-COMSOAL/S. To assess the effectiveness of MIP and 2-COMSOAL/S, a set of test problems are solved. The computational results show that 2-COMSOAL/S is very effective for the problem.     

基于启发式算法的电控板装配线线平衡优化

为了解决人员配置不稳定而导致的工位作业负荷不平衡问题,以某电控板装配企业为对象,构建其电控板装配线生产模型和线平衡优化模型。在该优化模型中,将约束条件转化为启发式规则,改进模型的参数设置和处理过程,将该模型转化为可求解的启发式算法。以该企业某电控装配线为例,通过线平衡优化实验证明该模型有效提高产量和线平衡率,说明该模型是有效和实用的。     

A Petri net-based heuristic for mixed-model assembly line balancing problem of Type-E

To effectively respond to the changing market demands, a manufacturer should produce variety of products with small lots. Thus, multiple products (models) are assembled simultaneously on a same line. However, it is very challenging to balance such an assembly line. This paper conducts a study on balancing a mixed-model assembly line of Type E. To solve this problem, a coloured-timed Petri net model is developed to describe the task precedence relationship. Also, the optimisation problem is formulated as a mathematical programming model. Then, with the models, a two-stage heuristic algorithm is proposed to solve the problem. At the first stage, based on the Petri net model, a P-invariant algorithm (PA) is presented to minimise the number of workstations. At the second stage, a heuristic is proposed to further minimise the cycle time by combining the PA with a binary search algorithm (BSA). Performance of the proposed method is evaluated by an illustrative example and numerical experiments. It is shown that it works well in terms of both solution accuracy and computational efficiency for large size problems.     

The type-II assembly line rebalancing problem considering stochastic task learning

Assembly lines with non-constant task time attribute are widely studied in the literature. For the SALBP-II assembly line balancing problem, we take account of stochastic task time changes, which is more practical than the deterministic times often assumed in industrial application. An algorithm – ENCORE, which leverages the traditional algorithm SALOME2, is proposed to address the assembly line balancing problem with stochastic task time attribute. Computational and statistical experiments are conducted to show the efficiency of proposed algorithms over traditional methods with regards to the improvement of total production times.     

随机型双边装配线平衡问题的一种启发式算法

为有效求解随机型双边装配线第Ⅰ类平衡问题(STALBP 1),在分析双边装配线平衡特点的基础上,考虑各任务操作时间的随机性,提出了一种启发式算法。在该启发式算法中,假定各任务的操作时间服从正态分布,运用具有操作方位约束的任务优先分配等规则来进行任务的选择和分配,通过改变预设超限概率,在不同生产节拍下,分别得到不同的平衡方案。实例验证了算法的有效性。     

Incorporating Physical Demand Criteria into Assembly Line Balancing

Many assembly line balancing algorithms consider only task precedence and duration when minimizing cycle time. However, disregarding the physical demands of these tasks may contribute to the development of work-related musculoskeletal disorders in the assembly line workers. Three line balancing heuristics that incorporate physical demand criteria were developed to solve the problem of finding assembly line balances that consider both the time and physical demands of the assembly tasks: a ranking heuristic, a combinatorial genetic algorithm, and a problem space genetic algorithm. Each heuristic was tested using 100 assembly line balancing problems. Incorporating physical demands using these algorithms does impact the assembly line configuration. Results indicated that the problem space genetic algorithm was the most adept at finding line balances that minimized cycle time and physical workload placed upon participants. Benefits of using this approach in manufacturing environments are discussed.