基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

基于杂合遗传算法的工艺路线可变Job Shop调度研究

提出一种将遗传算法与启发式规则、模拟退火法等搜索方法结合在一起的杂合遗传算法,用于求解工艺路线可变的JobShop调度问题。通过对某双极型集成电路封装企业的JobShop调度仿真,结果表明算法是有效和可行的。     

带有交货期窗口的单机加权提前／拖期调度问题研究

提前/拖期调度在JIT生产中具有重要意义,带有交货期窗口的调度问题是一个更一般的问题,但目前尚缺乏有效的求解方法.本文提出一种求解带有交货期窗口的单机提前/拖期调度问题的遗传算法,是为克服简单遗传算法的早熟收敛现象而提出的一种新型的遗传算法,并用大量随机产生的实例进行了仿真研究,结果表明,本文提出的算法是有效的.     

两阶段法求解混装模式下的加热炉调度

针对目前加热炉调度模型少有考虑混装模式下加热炉调度优化的不足,建立了连铸-热轧混装-体化模式下的加热炉生产调度优化模型,并提出了基于贪婪算法和模拟退火算法的两阶段求解方法.生产数据测试表明该模型和算法能有效解决加热炉调度问题.     

双边多工位装配线平衡的应用研究

为克服传统算法求解效率和求解质量低的缺陷,针对装配线每个工作站左右两边各有多个工位的装配线平衡问题,提出一种基于可行作业序列的遗传算法,既保留了传统GA的并行和随机搜索能力,同时又只在可行解子空间进行搜索,这样可提高算法运算效率和计算结果的精度。     

民航机场机位分配问题的遗传算法研究

本文通过对求解目标和所受约束条件的分析研究,提出了机场机位分配问题模型,设计了相应的遗传算法模型,并使用改进的遗传算法对问题进行了求解,实验结果表明,本文提出的改进策略是可行和有效的.本文研究成果已应用于国内某大机场的生产运营系统.     

SDN供需流的两阶段及其优化分析——基于木地板生产企业的视角

在传统企业向供需网企业转变过程中,作为SDN的一个供需流,其核心集中在对车间生产调度及物流配送的优化上.针对这两个问题,基于木地板生产企业的现状,本文引入了量子粒子群与模拟退火相结合的混合算法,以及一种求解物流系统的整合优化模型与求解的启发式算法分别对其进行研究,具有一定的实用价值.     

柔性资源约束下的产品开发项目优化调度研究

为解决具有柔性资源约束的产品开发项目调度问题,综合考虑项目调度过程中任务的先后约束关系、所需技能以及柔性资源等约束,以遗传算法和最大流理论为基础,提出了问题求解的改进遗传算法.该算法采用基于优先权的自然数编码,在解码过程中首先采用拓扑排序将染色体翻译成先后关系可行任务链表,然后运用网络最大流理论求解每项任务的柔性资源配置方案,并采用了适用于该问题的遗传操作.测试问题实验结果验证了算法的可行性和有效性.     

安装时间与次序相关的生产调度干扰管理研究

在安装时间和次序相关的单机调度问题中,为应对突发性的工件优先级变动造成的影响,构建了双目标重调度模型。原目标为生产的流程时间,扰动目标为工件的加工次序扰动。针对模型中的双目标,设计了基于有效解的两阶段混合启发式算法进行求解,在原目标和扰动目标之间进行权衡。混合算法第一阶段里,基于任意单个工件次序变化将双目标问题转化成单目标TSP问题,利用最近邻域和插入混合求得单目标问题的若干解,构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势,对初始种群进行扩展搜索,最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标,验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。     

基于GATS混合策略的多目标优化算法

用遗传算法求解多目标优化问题的难点在于适应值函数难以定义.本文提出一种定义多目标优化问题适应值函数的方式,使遗传算法不仅满足于得到一个决策方案,而是以得到问题的全部非劣解为目标,最终的决策方案由决策人根据自己的偏好来决定.同时为避免提前收敛现象,本文根据遗传算法和Tabu Search算法自身的特点,通过对二者的优势和不足进行分析,提出一种将二者混合使用的求解多目标优化问题的策略.它以遗传算法为基础,用遗传算法作全局搜索,用Tabu Search算法作局部搜索,改进遗传算法的计算结果.     

A flight scheduling model for Taiwan airlines under market competitions

In this research, we develop a short-term flight scheduling model with variable market shares in order to help a Taiwan airline to solve for better fleet routes and flight schedules in today's competitive markets. The model is formulated as a non-linear mixed integer program, characterized as an NP-hard problem, which is more difficult to solve than the traditional fixed market share flight scheduling problems, often formulated as integer/mixed integer linear programs. We develop a heuristic method to efficiently solve the model. The test results, mainly using the data from a major Taiwan airline's operations, show the good performance of the model and the solution algorithm.     

Economic Lot Scheduling Problem with Returns

Motivated by a case study of a company that produces car parts, we study the multi‐product economic lot scheduling problem for a hybrid production line with manufacturing of new products and remanufacturing of returned products. For this economic lot scheduling problem with returns (ELSPR), we consider policies with a common cycle time for all products, and with one manufacturing lot and one remanufacturing lot for each product during a cycle. For a given cycle time, the problem is formulated as a mixed integer linear programming (MIP) problem, which provides the basis for an exact solution. The application of this model for one of the core products of the case study company indicates a 16% reduction in cost compared to the current lot scheduling policy.     

舆情传播中考虑公众风险感知的多资源流应急优化调度

针对舆情传播背景下应急资源调度问题的特殊性,首先运用多案例分析进行了具体描述。然后,考虑到公众的有限理性,运用前景理论对其风险感知行为进行了刻画,并给出了保留供应率的定义。进一步,运用模糊理论来刻画公众追溯以往的资源供应状况,在同时考虑到供应点和配送中心的能力扩充基础上,构建了多种类资源应急优化调度的0-1混合整数非线性模糊规划模型。最后,以2011年东日本大地震事件为例验证了理论研究的有效性,并考查了决策者在控制公众风险感知中的偏好行为对最优调度方案的影响。     

Single machine scheduling: A comparison of two solution procedures

Recent research on the single machine scheduling problem has focused on the treatment of multiple scheduling objectives. Most works have used some combination of mean flowtime, maximum tardiness, or total tardiness as scheduling criteria. Previous research has largely ignored earliness as a scheduling criterion. This paper presents a model that employs the criteria of flowtime as a measure of work-in-process (WIP) inventory and total job earliness to represent finished goods inventory. Total tardiness is used to represent customer satisfaction. The three criteria are used to form a single, weighted-sum objective function for guiding the choice of the best processing sequence. Two procedures are presented that might be used to solve this problem. The first is an enumeration scheme using bounding and dominance criteria that have been developed to aid efficient solution, and the second is a mixed integer linear programming (LP) formulation. Computational experience with the two models is also presented.     

Collaborative optimization for metro train scheduling and train connections combined with passenger flow control strategy

For high-frequency metro lines, the excessive travel demand during the peak hours brings a high risk to metro system and a low comfort to passengers, so it is important to consider passenger flow control when designing the metro train scheduling strategy. This paper presents a collaborative optimization method for metro train scheduling and train connections combined with passenger control strategy on a bi-directional metro line. Specifically, the dynamic equations for the train headway and train passenger loads along the metro line, the turnaround operations and the entering/exiting depot operations are considered simultaneously. The proposed collaborative optimization problem is formulated as a mixed integer nonlinear programming model to realise the trade-off among the utilization of trains, passenger flow control strategy and the number of awaiting passengers at platforms, which is further reformulated into mixed integer linear programming (MILP) model. To handle the complexity of this MILP model, a Lagrangian relaxation-based approach is designed to decompose the original problem into two small subproblems, which reduces the computational burden of the original problem and can efficiently find a good solution of the train schedule and train connections problem combined with passenger flow control strategy. The numerical experiments are implemented to investigate the effectiveness of the proposed model and approach, which shows that the proposed model is not sensitive to uncertain passenger demand. Under the proposed collaborative optimization approach, the number of train service connections and the crowding inside stations and carriages with the proper passenger flow control strategy can be evidently balanced, and thereby the operation efficiency and safety of the metro lines are effectively improved.     

Integrated project operations and personnel scheduling with multiple labour classes

The main theme of this paper is improving project schedules by integrating the scheduling of project jobs and labour resources. An ILP model is presented of the integrated project operations and personnel scheduling problem with multiple labour categories. Traditionally, this problem is solved in two steps: first, operations are scheduled by solving the resource-constrained project scheduling problem; then, labour categories are scheduled by solving the personnel days-off scheduling problem. The proposed model combines the two stages into an integrated problem, which is solved in one step. Using 48 test problems, the two methods were compared in terms of total cost, labour cost and scheduling efficiency. The results clearly indicate that the integrated model outperforms the traditional two-step method.     

基于风险的考虑成本和允许等待的车辆运输调度问题研究

本文同时考虑了成本约束和允许等待情形,研究了最小化风险的车辆运输调度问题,其中运输风险是随时间不同而变化的,即研究在时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的顶点上决定的出发和等待时间的综合问题。建立了相应的混合整数规划模型,设计了相应的算法,并分析了算法复杂性,最后通过算例验证了该算法的有效性和可行性。     

An integrated modelling approach for raw material management in a steel mill

An integrated modelling approach combining optimisation models with simulation is proposed for coordinated raw material management at steel works throughout the whole supply chain management process. The integrated model is composed of three components: ship scheduling, yard operation simulation and material blending models. The ship scheduling model determines which brands, how much and when they should be arrived, and the problem is modelled as mixed integer linear programming. The simulation model is used to simulate the whole processes from ships’ arrivals to the retrieval of the materials through the berthing and unloading the raw materials. Finally, the raw material blending model is developed for determining the brand and quantity of raw materials to be used. The proposed integrated modelling approach for raw material management has been successfully implemented and applied at steelwork to provide shipping schedules and predict future inventory levels at stock yards. By coordinating all the activities throughout the entire raw material supply chain management process, this article proposes an integrated approach to the problem and suggests a guideline by the appropriate simplification. The quantitative nature of the optimisation model and simulation facilitates an assessment of the risk factors in the supply chain, leading to an evaluation of a wide variety of scenarios and the development of multiple contingency plans. Further research is expected to supplement the ship scheduling models with heuristics for the idiosyncratic constraints of maritime transportation.     

Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming

Flexibility, speed, and efficiency are major challenges for operations managers in today's knowledge-intensive organizations. Such requirements are converted into three production scheduling criteria: (a) minimize the impact of setup times in flexible production lines when moving from one product to another, (b) minimize number of tardy jobs, and (c) minimize overall production time, or makespan, for a given set of products or services. There is a wide range of solution methodologies for such NP-hard scheduling problems. While mathematical programming models provide optimal solutions, they become too complex to model for large scheduling problems. Simultaneously, heuristic approaches are simpler and very often independent of the problem size, but provide “good” rather than optimal solutions. This paper proposes and compares two alternative solutions: 0-1 mixed integer linear programming and genetic programming. It also provides guidelines that can be used by practitioners in the process of selecting the appropriate scheduling methodology.     

TECHNICAL NOTE: A SIMPLE MODEL FOR OPTIMIZING THE SINGLE MACHINE EARLY/TARDY PROBLEM WITH SEQUENCE-DEPENDENT SETUPS

A simple mixed integer programming model for the N job/single machine scheduling problem with possibly sequence-dependent setup times, differing earliness/tardiness cost penalties, and variable due dates is proposed and evaluated for computational efficiency. Results indicated that the computational effort required to reach optimality rose with the number of jobs to be scheduled and with decreased variance in due dates. Though computational effort was significant for the largest problems solved, the model remained viable for optimizing research scale problems.