单台批处理机生产运输协调合作博弈调度问题

研究单台批处理机生产与生产前运输的协调调度问题,目标函数为最小化与完成时间相关的生产总成本.以工件为博弈方,以联盟的最大成本节省为特征函数,将调度问题转换为合作博弈模型.针对相同运输时间与加工时间的情形,证明该合作博弈具有非空核,beta规则可得一个核分配.针对一般问题,设计Q-learning算法求解联盟最优调度,并利用beta规则对节省的成本进行分配.数值算例验证了合作博弈模型的可行性以及Q-learning算法与beta规则对节省成本分配的有效性.     

带有交货期的比例流水车间调度问题的合作博弈

针对具有多个客户订单的比例流水车间调度问题,在考虑有交货期及提前和拖期惩罚下,以客户支出成本为优化指标,在客户通过合作结成联盟的方式下,以联盟内成员进行重新调度所获得的最大成本节省为联盟的价值,建立合作博弈模型.该合作博弈是具有无外部性的平衡博弈,从而有非空核.考虑到客户对提前加工和延迟加工的迫切程度不同,提出基于提前及拖期惩罚的β规则分配方法,该方法能得到带有交货期的比例流水车间调度合作博弈的一个核分配.通过混合差分进化算法求解最优调度顺序,实验结果验证了基于合作博弈模型的调度方法及成本分配方法的有效性.     

求解混合流水车间调度问题的一种遗传算法

由于高度的计算复杂性(NP-hard问题),混合流水车间调度问题很难求得最优解,启发式算法和智能优化算法(如遗传算法)求解此类问题的近优解的有效性和实用性已被证实。该文提出了一种基于遗传算法的求解方法,在由染色体转换成可行调度的过程中引入工件插入方法,同时设计了一种新的交叉算子。通过大量的数值计算表明,该算法的优化质量大大优于传统的遗传算法和NEH启发式算法。     

混合流水车间调度的遗传下降算法

针对混合流水车间调度问题(Hybrid Flow Shop Scheduling,HFSS)建立了混合整数规划模型,提出了遗传下降算法(Genetic Descent Algorithm,GDA).GDA与HFSS工件在机器上最优分配规则相结合,不但能够产生初始可行解,而且保证交叉和变异后解仍然可行;同时在遗传算法中嵌入邻域下降策略.为了验证GDA算法的有效性,随机产生了230组数据进行实验.实验结果表明:对于HFSS问题,在小规模情况下,GDA算法与最优解之间的平均偏差为0.1%;对于较大规模的情况,GDA比NEH算法平均改进10.45%.     

两机无等待流水车间调度问题的性质

针对两机无等待流水车间调度问题,提出目标函数最大完工时间最小化的快速算法,并给出算法的复杂度。分析两机无等待流水车间调度问题的排列排序性质,证明了两机无等待流水车间调度问题的可行解只存在于排列排序中,排列排序的最优解一定是两机无等待流水车间调度问题的最优解。最后研究了同时包含普通工件和无等待工件的两机流水车间调度问题的复杂性,为进一步研究两机无等待流水车间调度问题提供了理论依据。     

求解多目标流水车间调度Pareto最优解的遗传强化算法

针对多目标流水车间调度Pareto最优问题, 本文建立了以最大完工时间和最大拖延时间为优化目标的多目标流水车间调度问题模型, 并设计了一种基于Q-learning的遗传强化学习算法求解该问题的Pareto最优解. 该算法引入状态变量和动作变量, 通过Q-learning算法获得初始种群, 以提高初始解质量. 在算法进化过程中, 利用Q表指导变异操作, 扩大局部搜索范围. 采用Pareto快速非支配排序以及拥挤度计算提高解的质量以及多样性, 逐步获得Pareto最优解. 通过与遗传算法、NSGA-II算法和Q-learning算法进行对比实验, 验证了改进后的遗传强化算法在求解多目标流水车间调度问题Pareto最优解的有效性.     

带运输时间混合流水车间成组调度的协同进化文化基因算法EI北大核心CSCD

研究了一类带有序列相关准备时间和阶段间运输时间的混合流水车间成组调度问题,以最小化最大完工时间为目标建立混合整数线性规划模型,结合问题特征提出一种协同进化文化基因算法.算法采用置换序列的方式对工件组间调度、各工件组内工件间调度以及各工件组在各阶段上并行机的指派3个子问题进行统一编码,基于负载均衡思想和改进的先到先得策略将染色体解码为问题的可行解;进化过程中采用多种遗传算子执行全域搜索,并设计了一种基于破坏和重新构造的协同进化局部搜索策略.通过不同问题规模的数据实验和与对比算法的比较分析,验证了所提模型和算法的有效性.     

缓冲区有限的流水车间调度问题的启发式算法

针对缓冲区有限的流水车间调度问题,分析了目标函数的特征,及目标函数与工件空闲时间之间的关系,设计开发了启发式算法。算法将以Makespan为目标函数转化成以最小化机器空闲时间为目标函数,并以此为基础构造初始加工序列,再通过贪婪排序与插入寻优消除缓冲区受限约束并寻找问题的近优解。仿真实验结果表明,算法在求解质量和计算时间方面明显优于其他几种排序规则,并体现了目标函数表达式结构的特性及对解的适应性。     

新型离散蝙蝠算法求解柔性流水车间调度问题

针对以最小化完工时间为目标的柔性流水车间调度问题,提出了一种新型离散蝙蝠算法。介绍了蝙蝠算法的基本思想,重新定义速度与位置的加法操作来实现粒子的位移,给出了算法的具体实现方案。通过实例仿真和算法比较验证了算法的优化性能,实验结果表明该算法可以有效地求解柔性流水车间调度问题。     

基于新邻域结构的Memetic 算法求解流水车间调度问题

流水车间调度是一类典型的生产调度问题,属于NP-难问题.针对传统的最优化方法难以求解大规模问题,提出了一个Memetic算法,在算法的局部搜索中使用一种新型的基于NEH的邻域结构,并且其邻域规模随着搜索的进行能够动态变化,可以大大提高算法的搜索能力.通过对标准Benchmark问题的测试,所得结果表明提出的基于新邻域结构的Memetic算法具有较好的性能,并且优于已有文献中的粒子群算法.     

Inverse scheduling: two-machine flow-shop problem

We study an inverse counterpart of the two-machine flow-shop scheduling problem that arises in the context of inverse optimization. While in the forward scheduling problem all parameters are given and the objective is to find job sequence(s) for which the value of the makespan is minimum, in the inverse scheduling the exact values of processing times are unknown and they should be selected within given boundaries so that pre-specified job sequence(s) become optimal. We derive necessary and sufficient conditions of optimality of a given solution for the general case of the flow-shop problem when the job sequences on the machines can be different. Based on these conditions we prove that the inverse flow-shop problem is NP-hard even in the case of the same job sequence on both machines and produce a linear programming formulation for a special case which can be solved efficiently.     

A bicriteria two-machine flow-shop serial-batching scheduling problem with bounded batch size

We consider the two-machine flow-shop serial-batching scheduling problem where the machines have a limited capacity in terms of the number of jobs. Two criteria are considered here. The first criterion is the number of batches to be minimized. This criterion reflects situations where processing of any batch induces a fixed cost, which leads to a total cost proportional to the number of batches. The second criterion is the makespan. This model is relevant in different production contexts, especially when considering joint production and inbound delivery scheduling. We study the complexity of the problem and propose two polynomial-time approximation algorithms with a guaranteed performance. The effectiveness of these algorithms is evaluated using numerical experiments. Exact polynomial-time algorithms are also provided for some particular cases.     

Minimising mean tardiness with alternative operations in two-machine flow-shop scheduling

This paper describes the development of a mixed binary integer programming (BIP) model for scheduling alternative operations in two-machine flow-shop problems with mean tardiness as the criterion. Although the mixed BIP model provides an optimal solution, its variables and constraints increase drastically as the number of jobs increases. Therefore, an optimal solution is not always attainable within the allowable time by solving the mixed BIP model. Consequently, two heuristics suitable for the formulated scheduling problems are proposed. Computational experiments are conducted to test the accuracy and efficiency of the heuristics in generating near optimal solutions for minimising the mean tardiness of jobs.     

传搁时间约束下的运输与批处理机生产协调调度

针对炼钢模铸系统钢锭高温运作的特点,提出带有传搁时间约束的生产前运输与批处理机生产协调的调度问题.工件的加工时间依赖于其传搁时间,每批工件的加工时间为该批工件中加工时间最大值.目标函数为最小化总完工时间与生产费用的线性组合.通过复杂性分析,证明该问题是强NP难解问题.建立混合整数规划模型,基于动态规划提出两种特殊情况的最优算法,设计原问题的启发式算法并进行最坏情况下性能比分析.实验仿真结果验证了所提出启发式算法的有效性与稳定性.     

A new encoding scheme-based hybrid algorithm for minimising two-machine flow-shop group scheduling problem

This article investigates the two-machine flow-shop group scheduling problem (GSP) with sequence-dependent setup and removal times, and job transportation times between machines. The objective is to minimise the total completion time. As known, this problem is an NP-hard problem and generalises the typical two-machine GSPs. In this article, a new encoding scheme based on permutation representation is proposed to transform a random job permutation to a feasible permutation for GSPs. The proposed encoding scheme simultaneously determines both the sequence of jobs in each group and the sequence of groups. By reasonably combining particle swarm optimisation (PSO) and genetic algorithm (GA), we develop a fast and easily implemented hybrid algorithm (HA) for solving the considered problems. The effectiveness and efficiency of the proposed HA are demonstrated and compared with those of standard PSO and GA by numerical results of various tested instances with group numbers up to 20. In addition, three different lower bounds are developed to evaluate the solution quality of the HA. Limited numerical results indicate that the proposed HA is a viable and effective approach for the studied two-machine flow-shop group scheduling problem.     

A two-machine flowshop scheduling problem with a separated maintenance constraint

This paper considers a two-machine flowshop scheduling problem with a separated maintenance constraint. This means that the machine may not always be available during the scheduling period. It needs a constant time to maintain the machine after completing a fixed number of jobs at most. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem has some practical applications, for example, in electroplating process, the electrolytic cell needs to be cleaned and made up a deficiency of medicine. In this paper, we propose a heuristic algorithm to solve this problem. Some polynomially solvable cases and computational experiments are also provided.     

Heuristics for two-machine no-wait flowshop scheduling with an availability constraint

In this paper we study the two-machine no-wait flowshop problem with an availability constraint. The problem has been shown to be NP-hard, and some heuristics with a worst-case error bound of 2 have been developed for it. We provide two improved heuristics for the problem, and show that each has a worst-case error bound of 5/3.     

Two-machine flowshop scheduling with intermediate transportation under job physical space consideration

In this paper, we study a coordinated production–transportation scheduling problem in a two-machine flowshop environment where a single transporter may carry several jobs simultaneously as a batch between the machines. Each job has its own physical-space requirement while being loaded into the transporter. The goal is to minimize the makespan. For the jobs with the same size of physical space during transportation, we present a heuristic algorithm with an absolute worst-case ratio of 2 and a polynomial-time optimal algorithm for a special case with given job sequence. For the jobs having different size of physical storage space, a heuristic algorithm is constructed with an absolute worst-case ratio of 7/3 and asymptotic worst-case ratio of 20/9. Computational experiments demonstrate that the two heuristic algorithms developed are capable of generating near-optimal solutions quickly.     

运输能力有限的分段两阶段多车间调度问题

为有效解决船舶分段生产过程中存在的返工、运输能力限制以及堆场面积约束等问题,分析两阶段多车间调度的特点,构建了运输能力有限的分段两阶段多车间调度模型。模型综合考虑了分段批次内重调度、批次间的分割合并、分段返工以及缓冲面积和运输能力约束,目标是最小化分段的最大完工时间,建立分段在加工车间、装配车间以及堆场中的调度数学模型。利用基于路径选择的分段两阶段多车间调度启发式算法进行求解,并通过数值实验以及对比分析验证了模型的合理性和算法的有效性。