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

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

工件可拒绝的有限等待置换流水车间调度算法

有限等待限定了工件在相邻机器间的等待时间上下限,普遍存在于中间产品性质不稳定且存在运输作业的车间环境中.工件可拒绝的有限等待置换流水车间调度是对工件拒绝和工件调度的联合决策,要求确定拒绝工件集合并给出被接受工件的调度方案.针对这一联合决策问题,以最小化总拒绝成本与总拖期成本之和为目标,并为最大完工时间(Makespan)设置上限约束,结合问题特征提出一种协同进化遗传算法.该算法将染色体编码分解为工件拒绝和工件序列两个子集,基于调度规则生成初始种群,引入协同进化策略依次进化子集种群,并提出基于记忆的动态概率参数设计方法以确定遗传算子的执行概率,设计解码规则以保证解的可行性并优化总成本.最后,通过数据实验验证了所提出算法及相关策略的可行性和有效性,并分析了问题参数对算法性能的影响.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

基于TSP方法求解等待时间受限的置换流水车间调度

等待时间受限的置换流水车间调度问题要求工件在连续两个机器间的等待时间满足上限值约束.对此,分析了工件序列中相邻工件的加工持续时间及其上下界关系,并且提出一种启发式方法.首先,建立旅行商间题（TSP）以生成初始调度;然后,采用扩展插入方法优化调度解.为了衡量算法性能,给出问题下界的计算方法和相关评价指标,并通过数据实验验证了该启发式和下界计算方法的可行性和有效性.     

带有线性恶化工件和释放时间的两个代理单机调度问题

研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题. 所有工件在一台机器上加工, 每个代理有各自依赖于自己工件的优化目标. 针对工件释放时间相同与不同两种情况, 研究了有约束的优化模型, 即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界. 当工件具有相同的释放时间, 我们主要考虑的目标函数有: 总加权完工时间和总加权拖期工件数. 当工件具有不同释放时间, 我们考虑的目标函数有: 最大完工时间、总完工时间以及拖期工件数. 对于每一个问题, 我们分析了问题的计算复杂性. 此外, 对于NP难问题的一些特殊情况本文分析了最优解性质, 基于这些性质给出了最优算法.     

带负载均衡的混合算法求解分布式异构作业车间调度问题

针对以最小化最大完工时间为目标的分布式异构作业车间调度问题(DHJSP), 本文提出了一种新的混合遗传禁忌搜索算法. 首先, 综合考虑工厂的工件总负载与最大机器负载, 提出了一种新的工厂负载表达方式. 其次, 针对DHJSP总工序数不定的特性, 提出以最小化最大工厂负载为目标快速确定初始工件分配方案, 并验证了方法的高效性. 然后, 新设计了两种考虑负载均衡的单工件转移邻域结构, 根据工序调度的结果对工件分配方案进行局部搜索. 最后, 因DHJSP缺少标准算例和相关算法, 在分布式同构作业车间调度问题(DJSP)上与现有算法进行对比, 所提算法在TA算例的480个问题上更新了420个问题的最优解, 其余60个问题取得了同等最优解. 在随机生成的3个不同规模的异构算例中, 所提算法也均取得了较好解, 验证了所提方法的优越性.     

双目标无等待流水线调度的加权混合算法

针对最小化“总完工时间”和“最大完工时间”的双目标无等待流水线作业调度问题提出了一种粒子群加权混合优化算法,通过随机加权的方式将其转换成单目标问题,并应用基于升序排列的ROV（ranked-order-value）编码规则,将粒子群优化算法应用于无等待流水线作业调度问题。为了提高算法的性能,增强算法的搜索能力,提出的混合算法应用了NEH方法构造初始种群,在一个较好的初始值上进行粒子群优化,为防止种群陷入局部最优造成早熟,在粒子群每次迭代之后对全局最优解加入扰动并进行变邻域搜索。仿真实验结果表明该混合调度算法具有良好的性能。     

遗传算法求解单目标柔性流水车间调度问题研究

为了研究单目标的柔性流水车间的调度问题,完成对此类复杂的组合优化问题的求解,求最小化最大完工时间,提出解决该问题的方法为通过遗传算法对所有解空间进行全局搜索最优解。并且用此方法在进行加工机器选择时用轮盘赌的方法来选择个体,达到优化初始种群的目的。接着对此不确定问题的进行数学模型的建立,确定优化总目标为所有待加工工件加工完成的最小化完工时间。然后通过遗传算法对问题模型求解最优解和最优调度方案。最后,用Matlab进行模拟仿真求出最优结果。     

批量流水调度问题的量子候鸟协同优化算法

为了求解批量流水调度问题（LFSP）的最小化最大完工时间,提出一种量子候鸟协同优化（QMBCO）算法。首先,采用Bloch量子球面编码方案扩大解空间;然后,运用FL算法优化初始解,以弥补传统随机初始解的不足,保证初始种群具有较高的质量;最后,使用候鸟优化（MBO）算法及变邻域搜索（VNS）算法进行迭代,增强算法的全局搜索能力。采用随机生成不同规模的实例仿真,将QMBCO算法与目前较优的离散粒子群优化（DPSO）算法、MBO算法和量子布谷鸟协同搜索（QCCS）算法相比较。结果表明,在两种不同运行时间下QMBCO与DPSO、MBO、QCCS相比产生的最优解平均百分比偏差（ARPD）分别平均下降65%、34%和24%,证明了QMBCO算法的有效性和高效性。     

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

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

单机模糊加工时间下最迟开工时间调度问题

研究单机模糊加工时间下确定最迟开工时间的调度问题。目标是在满足每个工作都以大于等于各自指定的隶属度属于完工集合的约束下,建筑工作的最大最迟开工时间。通过模糊数学知识对模型进行分析,对于特殊情况给出了问题的最优解,对于一般情况给出了一个最优解的必要条件。     

On the identical parallel-machine rescheduling with job rework disruption

This paper investigates an issue of rescheduling on identical parallel machines where the original jobs have already been scheduled to minimize the total completion time, when a single set of jobs to be reworked re-arrives and creates a job rework disruption. Two conflicting rescheduling criteria are considered: the total completion time, as the measure of scheduling cost (efficiency); and the number of jobs assigned to different machines in the original schedule and newly generated schedule, as the measure of disruption cost (stability). Further, the rescheduling problem is defined as a bi-criteria scheduling problem. Two polynomial time algorithms are proposed to lexicographically optimize the two criteria. Besides, the set of all efficient schedules with respect to the two criteria can be also generated in polynomial time.     

Scheduling a single machine with concurrent jobs for the frozen food industry

This study examines the air blast freezing process of the frozen food industry, which processes multiple products with variable processing rates. The analysis depicts a new, single machine-scheduling problem in which the machine can process multiple jobs concurrently, within its capacity. The machine processes independent jobs arriving at various times while incurring interruption costs when allowing the jobs to enter or leave the machine. A mixed integer linear programming (MILP) model and a heuristic algorithm are developed for scheduling, the objectives of which are to minimize the costs associated with machine activities including that of waiting to load, waiting to unload and interruption time. The heuristic algorithm demonstrates the high potential of the computational time savings by obtaining the solution within one-fifth of the mathematical model computational time.     

Service Time Optimization of Mixed-Line Flow Shop Systems

We consider deterministic mixed-line flow shop systems that are composed of controllable and uncontrollable machines. Arrival times and completion deadlines of jobs are assumed to be known, and they are processed in the order they arrive at the machines. We model these flow shops as serial networks of queues operating under a non-preemptive first-come-first-served policy, and employ max-plus algebra to characterize the system dynamics. Defining completion-time costs for jobs and service costs at controllable machines, a non-convex optimization problem is formulated where the control variables are the constrained service times at the controllable machines. In order to simplify this optimization problem, under some cost assumptions, we show that no waiting is observed on the optimal sample path at the downstream of the first controllable machine. We also present a method to decompose the optimization problem into convex subproblems. A solution algorithm utilizing these findings is proposed, and a numerical study is presented to evaluate the performance improvement due to this algorithm.      

考虑机器故障的HFS重调度研究

针对机器故障下的混合流水车间重调度问题,在考虑工序等待时间受限约束的前提下,建立了以最大化重调度前后方案完工时间相似度和机器指派一致性为目标的重调度模型,并设计了自适应遗传算法对其进行求解。仿真实验结果表明,该模型和算法是有效的。     

Hadoop下资源匹配最大集作业调度算法

针对目前层级队列作业调度算法中资源占比高的作业执行效率低的问题,提出一种资源匹配最大集算法。该算法分析作业特征,引入完成度、等待时间、优先级、重调度次数为紧迫值因子,优先考虑资源占比高或等待时间长的作业,以改善作业公平性;采用双队列结构在可用资源总量内优先选择高紧迫值作业,在不同资源占比作业集比较中选择作业数最大集,以实现调度平衡。在与最大最小公平(Max-min fairness)算法的实例对比中发现,该算法可降低作业集平均等待时间、提高资源利用率。实验对比结果表明,该算法可将不同资源占比的单一类型作业集执行时间缩短18.73%,其中资源占比高的作业执行时间缩短27.26%;在混合型作业集中对应的执行时间可分别缩短22.36%与30.28%。所提算法能有效减少资源占比高作业的等待,提高作业整体执行效率。     

Single facility scheduling with nonlinear processing times

This paper considers the static single facility scheduling problem where the processing times of jobs are a monotonically increasing function of their starting (waiting) times and the objective is to minimize the total elapsed time (called the makespan) in which all jobs complete their processing. Based on the combinatorial analysis of the problem, an exact optimization algorithm is developed for the general processing time function which is then specialized for the linear case. In view of the excessive computational burden of the exact optimization algorithm for the nonlinear processing time functions, heuristic algorithms are proposed. The effectiveness of these proposed alogrithms is empirically evaluated and found to indicate that these heuristic algorithms yield optimal or near optimal schedules in many cases.     

Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm

This research investigates a two-stage hybrid flowshop scheduling problem in a metal-working company. The first stage consists of multiple parallel machines and the second stage has only one machine. Four characteristics of the company have substantiated the complexity of the problem. First, all machines in stage one are able to process multiple jobs simultaneously but the jobs must be sequentially set up one after another. Second, the setup time of each job is separated from its processing time and depends upon its preceding job. Third, a blocking environment exists between two stages with no intermediate buffer storage. Finally, machines are not continuously available due to the preventive maintenance and machine breakdown. Two types of machine unavailability, namely, deterministic case and stochastic case, are identified in this problem. The former occurs on stage-two machine with the start time and the end time known in advance. The latter occurs on one of the parallel machine in stage one and a real-time rescheduling will be triggered. Minimizing the makespan is considered as the objective to develop the optimal scheduling algorithm. A genetic algorithm is used to obtain a near-optimal solution. The computational results with actual data are favorable and superior over the results from existing manual schedules.     

Solving single machine scheduling under disruption with discounted costs by quantum-inspired hybrid heuristics

In this paper we study machine disruption on scheduling problem. We focus on the case where the weighted discounted shortest processing time (WDSPT) rule is optimal for original single machine scheduling problem. After a subset of jobs have finished processing, we learn that the machine would be disrupted for some period of time in the future. Therefore a new schedule is needed considering both original objective and the deviation from the initial schedule. The original objective is measured by the weighted discounted total completion time and the deviation is measured by the variances in jobs’ completion times. According to the characteristics of optimal schedule, we design one hybrid heuristic algorithm, combining the advantages of qubit representation in quantum computing and Non-dominated Sorting Genetic Algorithm (NSGA-II). By analyzing the solutions diversity and proximity to optimal Pareto front on several metrics, we demonstrate that the proposed algorithm is effective for machine disruption management.     

Resource optimal control in some single-machine scheduling problems

We consider a problem to schedule a set of jobs on a single machine under the constraint that the maximum job completion time does not exceed a given limit. Before a job is released for processing, it must undergo some preprocessing treatment which consumes resources. It is assumed that the release time of a job is a positive strictly decreasing continuous function of the amount of resources consumed. The objective is to minimize the total resource consumption. We show that ordering jobs in nonincreasing processing times yields an optimal solution. We then consider a bicriterion approach to the problem in which the maximum job completion time and the resource consumption are simultaneously minimized and present a polynomial time solution algorithm. Finally, we consider a related problem in which the job release times are given but the processing times are functions of the amount of resource consumed. We show that ordering jobs in nondecreasing release times gives an optimal solution and that the problem to minimize both the maximum completion time and resource consumption is polynomially solvable