考虑柔性机器检修的钢管热轧批量调度方法

本文从无缝钢管生产管理中提取并定义了周期性机器柔性检修环境下的钢管热轧批量调度问题,针对无缝钢管热轧阶段的生产特点,将其抽象为一类考虑序列相关设置成本和机器柔性检修的单机调度问题,建立了以最小化机器闲置时间和机器调整时间为优化目标的数学模型。分析闲置时间和检修时点的关系,证明了闲置时间最小化性质,结合问题特征设计了两阶段启发式算法。算法第一阶段采用最小轧机调整时间规则获取具有最小机器调整时间的初始批量轧制序列,第二阶段对初始轧制序列进行全局寻优搜索。基于实际生产数据设计了多种问题规模的对比实验,实验结果表明模型和算法对求解该类问题具有较好效果。     

考虑机器检修的热轧钢管批量计划方法

本文从无缝钢管生产实际中提取并定义了周期性机器检修环境下的钢管热轧批量计划问题,基于无缝钢管生产的特殊性,将该问题抽象为一类考虑机器检修和机器调整时间的单机调度问题,并建立了以最小化机器闲置和机器调整时间为目标的数学模型.针对批量间的机器调整时间取决于钢管规格的变化这一特性,提出了最小调整时间排序规则,证明了该规则在不考虑检修计划时具有最优性.进而,以此为基础建立了循环求解框架,并设计了两阶段启发式算法.基于实际生产数据设计了多种问题规模的实验,验证了算法的有效性,并从实际应用角度对结果进行了分析.     

考虑加热炉生产因素的热轧板坯轧制计划模型与算法

加热炉生产是影响热轧机组利用率和轧制计划质量的重要环节之一.通过分析加热炉对热轧生产的影响,抽取板坯标准在炉时间和出炉温度这两个关键因素,建立热轧板坯轧制计划的整数规划模型,并提出自适应邻域搜索算法.在算法中设计约束满足策略、自适应搜索策略和反向学习邻域搜索策略.约束满足策略针对目标特征和加热炉因素设计两种值选择规则,用于生成高质量初始解;自适应搜索策略能够自主选择邻域结构和终止邻域搜索,有效优化邻域结构选择方式和算法收敛速度;反向学习邻域搜索策略基于反向学习技术增强解空间多样性,提高全局搜索能力.基于实际生产数据设计多种规模的实验,通过实验验证了算法的有效性.     

零等待约束下多产品间歇过程的多目标调度

针对零等待约束下多产品间歇过程的总流程时间和完工时间最小化问题,提出一种多目标离散组搜索算法求解.在采用启发式规则产生初始解的基础上,通过发现者、追随者和巡逻者的操作设计,算法不断更新Pareto前沿,同时,混合了基于插入邻域的多目标局部搜索方法.大量计算实验表明,所提出的算法获得的非支配解集在IGD和Set Coverage指标上优于非支配排序遗传算法和模拟退火算法,可为多目标决策者提供更好的决策依据,利于间歇生产过程的优化运行.     

变邻域搜索算法求解机器人制造单元调度问题——排序依赖转换时间

针对排序依赖转换时间的两机器机器人制造单元调度问题的NP难特性,设计了变邻域搜索算法求解。为了加快算法收敛速度,设计了工件阻塞时间最小化生成初始解;为了搜索到更好解,分析了算法的参数取值。通过随机产生算例测试,提出算法优于模拟退火算法,证实了提出算法的有效性。     

混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度

研究每阶段含不相关并行机的分布式柔性流水线调度问题.考虑顺序相关准备时间和工件动态到达时间,以最小化总加权提前/拖期惩罚为目标建立整数规划模型,提出一种融合离散差分进化算法、变邻域下降算法和局域搜索的混合离散人工蜂群算法以获取近优解.该算法采用基于工厂-工件号的编码以及基于机器最早空闲时间的动态解码机制,通过随机规则和均衡分派策略生成初始工厂-工件序列群,在引领蜂阶段引入离散差分进化算法产生优质工厂-工件序列,在跟随蜂阶段利用变邻域下降算法在被选择序列附近继续搜索以得到邻域序列,在侦察蜂阶段设计基于关键/非关键工厂间插入的局域搜索提高算法搜索能力.通过仿真实验测试不同规模的算例,实验结果表明,所提出的混合离散人工蜂群算法表现出较好的求解性能.     

改进萤火虫算法求解多目标柔性作业车间调度

针对多目标柔性作业车间调度问题,以最小化最大完工时间、最小化机器总负荷、最小化机器最大负荷为目标,提出一种改进邻域结构的离散萤火虫算法。首先,采用多种策略相结合的方式初始化种群,提高算法初始解质量以及种群多样性;其次,通过改进关键路径的邻域结构并设计离散萤火虫算法的位置更新公式,以增强算法全局搜索和局部搜索能力;最后,将该算法应用于标准数据集,并将求解结果与其他算法进行对比,验证了所提算法的有效性。     

多目标启发式狼群算法求解不相关并行机分批调度问题

针对考虑机器加工约束的不相关并行机分批调度问题,以工件种类切换次数和机器启停评价函数为优化目标,提出一种多目标启发式狼群算法进行求解。该算法在生成初始种群的过程中,融入列表反向学习和基于机器加工效率的启发式策略,并设计了一种不规则实数矩阵编码方式来实现任务分批。采用局部和全局邻域搜索相结合的方式实现狼群算法中智能行为搜索,通过分批调整学习机制对当前结果进行邻域搜索,利用改进整数解Pareto非支配排序方式循环迭代。最后通过不同规模实际算例测试和相关算法比较,验证了该算法的有效性和优越性。     

具有多种产品类型的最小订单提前/拖期问题

针对单机多产品多订单有序独立机器调整时间的订单排产问题,建立了以最小化订单 的提前和拖期罚值总和为优化目标的混合整数规划模型,分析了问题的NP-hard性和最优排序 中临近批组的优化特性,提出一个基于过滤束搜索的拟多项式时间算法,算法复杂性分析和仿真结 果验证了算法的有效性.     

混合遗传算法求解含机器可利用约束的HFSP

针对含机器阻塞和可利用约束的混合流水车间调度优化问题,考虑工件运输时间,以最小化总加权完工时间为优化目标,建立混合整数规划模型,提出一种基于启发式规则的自适应混合遗传算法求解该模型.在传统遗传算法的基础结构上,引入五种启发式规则生成部分初始种群,从而改善部分初始解的质量;设计分段自适应交叉概率和变异概率计算公式,以加快算法收敛;利用局域搜索对得到的调度解进行再次优化,进一步提高算法搜索能力.对不同规模问题进行仿真实验,结果验证了该算法的可行性和有效性.     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.     

Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach

In scheduling problems, taking the sequence-dependent setup times into account is one of the important issues that have recently been considered by researchers in the production scheduling field. In this paper, we consider flexible job-shop scheduling problem (FJSP) with sequence-dependent setup times to minimize makespan and mean tardiness. The FJSP consists of two sub-problems from which the first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on all machines. To solve this problem, a variable neighborhood search (VNS) algorithm based on integrated approach is proposed. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed the search process. To search the solution space, the internal loop used two main search engines, i.e. shake and local search procedures. In addition, neighborhood structures related to the sequencing problem and the assignment problem were employed to generate neighboring solutions. To evaluate the performance of the proposed algorithm, 20 test problems in different sizes are randomly generated. Consequently, computational results and comparisons validate the quality of the proposed approach.     

A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines

In this paper, we discuss a flexible flow shop scheduling problem with batch processing machines at each stage and with jobs that have unequal ready times. Scheduling problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). We are interested in minimizing the total weighted tardiness of the jobs. We present a mixed integer programming formulation. The batch scheduling problem is NP-hard. Therefore, an iterative stage-based decomposition approach is proposed that is hybridized with neighborhood search techniques. The decomposition scheme provides internal due dates and ready times for the jobs on the first and second stage, respectively. Each of the resulting parallel machine batch scheduling problems is solved by variable neighborhood search in each iteration. Based on the schedules of the subproblems, the internal due dates and ready times are updated. We present the results of designed computational experiments that also consider the number of machines assigned to each stage as a design factor. It turns out that the proposed hybrid approach outperforms an iterative decomposition scheme where a fairly simple heuristic based on time window decomposition and the apparent tardiness cost dispatching rule is used to solve the subproblems. Recommendations for the design of the two stages with respect to the number of parallel machines on each stage are given.     

An effective discrete invasive weed optimization algorithm for lot-streaming flowshop scheduling problems

Lot-streaming scheduling problem has been an active area of research due to its important applications in modern industries. This paper deals with the lot-streaming flowshop problem with sequence-dependent setup times with makespan criterion. An effective discrete invasive weed optimization (DIWO) algorithm is presented with new characteristics. A job permutation representation is utilized and an adapted Nawaz–Enscore–Ham heuristic is employed to ensure an initial weed colony with a certain level of quality. A new spatial dispersal model is designed based on the normal distribution and the property of tangent function to enhance global search. A local search procedure based on the insertion neighborhood is employed to perform local exploitation. The presented DIWO is calibrated by means of the design of experiments approach. A comparative evaluation is carried out with several best performing algorithms based on a total of 280 randomly generated instances. The numerical experiments show that the presented DIWO algorithm produces significantly better results than the competing algorithms and it constitutes a new state-of-the-art solution for the lot-streaming flowshop problem with sequence-dependent setup times with makespan criterion.     

求解流水车间批量流集成调度的离散入侵杂草优化算法

提出一种离散入侵杂草优化算法,用来解决最大完工时间目标的流水车间批量流集成调度问题.该调度问题包含两个紧密耦合的子问题:批次分割问题和考虑启动时间的批次调度问题.设计了两段字符串编码,用来表示两个子问题.与基本入侵杂草优化算法不同,所提算法基于适应度和年龄确定杂草种子数量,基于正切函数和连续邻域操作产生种子.8种邻域算子的混合应用与局部搜索增强了算法的求解能力.仿真实验表明了所提算法的有效性.     

An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups

In many real-world production systems, it requires an explicit consideration of sequence-dependent setup times when scheduling jobs. As for the scheduling criterion, the weighted tardiness is always regarded as one of the most important criteria in practical systems. While the importance of the weighted tardiness problem with sequence-dependent setup times has been recognized, the problem has received little attention in the scheduling literature. In this paper, we present an ant colony optimization (ACO) algorithm for such a problem in a single-machine environment. The proposed ACO algorithm has several features, including introducing a new parameter for the initial pheromone trail and adjusting the timing of applying local search, among others. The proposed algorithm is experimented on the benchmark problem instances and shows its advantage over existing algorithms. As a further investigation, the algorithm is applied to the unweighted version of the problem. Experimental results show that it is very competitive with the existing best-performing algorithms.     

A neighborhood for complex job shop scheduling problems with regular objectives

Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer limitations, and have pursued objectives that are more practically relevant than the makespan, such as total flow time and total weighted tardiness. However, most proposed solution approaches are tailored to the specific scheduling problem studied and are not applicable to more general settings. This article proposes a neighborhood that can be applied for a large class of job shop scheduling problems with regular objectives. Feasible neighbor solutions are generated by extracting a job from a given solution and reinserting it into a neighbor position. This neighbor generation in a sense extends the simple swapping of critical arcs, a mechanism that is widely used in the classical job shop but that is not applicable in more complex job shop problems. The neighborhood is embedded in a tabu search, and its performance is evaluated with an extensive experimental study using three standard job shop scheduling problems: the (classical) job shop, the job shop with sequence-dependent setup times, and the blocking job shop, combined with the following five regular objectives: makespan, total flow time, total squared flow time, total tardiness, and total weighted tardiness. The obtained results support the validity of the approach.     

An efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization

We confront the job shop scheduling problem with sequence-dependent setup times and weighted tardiness minimization. To solve this problem, we propose a hybrid metaheuristic that combines the intensification capability of tabu search with the diversification capability of a genetic algorithm which plays the role of long term memory for tabu search in the combined approach. We define and analyze a new neighborhood structure for this problem which is embedded in the tabu search algorithm. The efficiency of the proposed algorithm relies on some elements such as neighbors filtering and a proper balance between intensification and diversification of the search. We report results from an experimental study across conventional benchmarks, where we analyze our approach and demonstrate that it compares favorably to the state-of-the-art methods.