带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.     

基于工件间隙的Blocking流程车间调度启发式算法

考虑Blocking流程车间调度的特殊性质,提出一种基于工件间隙以达到减少机器闲置和工件滞留时间的初始排序规则,结合插入搜索机制,构造解决Blocking流程车间的调度问题的启发式算法.通过大量的计算实验并与有效地解决该调度问题的NEH算法进行比较,结果表明本算法在解的质量上有改进.     

禁忌搜索算法解决零空闲流水线调度问题

针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型.新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能.利用动态方式更新禁忌表长,提高了新算法的鲁棒性.为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法.仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值.     

基于损益云模型的制造车间重调度决策方法

针对制造车间重调度触发机制问题,建立了制造车间重调度损益函数,揭示了生产车间重调度过程损失及增益的变化规律.引入云理论测度重调度损益的不确定性,使用逆向云算法计算重调度增益云和损失云的数字特征,根据云形态预测重调度损益变化趋势.提出一种基于损益云模型的重调度决策方法以判断是否需要重调度,并利用最佳损益比甄选预调度方案以兼顾生产系统的稳定性和有效性.最后,通过实例验证了该方法的合理性和实用性.     

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

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

改进离散粒子群算法求解柔性流水车间调度问题

针对以最小化完工时间为目标的柔性流水车间调度问题(FFSP),提出了一种改进离散粒子群(DPSO)算法.所提算法重新定义粒子速度和位置的相关算子,并引入编码矩阵和解码矩阵来表示工件、机器以及调度之间的关系.为了提高柔性流水车间调度问题求解的改进离散粒子群算法的初始群体质量,通过分析初始机器选择与调度总完工时间的关系,首次提出一种基于NEH算法的最短用时分解策略算法.仿真实验结果表明,该算法在求解柔性流水车间调度问题上有很好的性能,是一种有效的调度算法.     

基于需求优先的多目标柔性车间调度研究

为满足按时提交客户货物的要求,需要优化企业的生产调度,现实的生产调度问题是传统车间调度问题的扩充,具有多目标、柔性等特性。针对柔性作业车间调度的需要,提出了在精益制造下的基于需求优先的多目标柔性车间调度算法。该算法以工件提前／拖期惩罚代价最小,调度最小生产周期为目标,基于规则的改进启发式调度,在调度过程中通过需求日期计算工件的优先级为每道工序分配合适的机器进行加工,可得到满意的较优解。与其他方法进行对比试验的结果表明,该算法在求解柔性作业车间调度问题是有效的。     

工件工序可并行的作业车间调度模型与求解

针对传统作业车间调度模型没有考虑工件工序存在并行性的不足,提出一种以最小化完工时间为目标的工件工序可并行作业车间调度模型,且在模型中考虑了工序加工设备柔性;设计了基于遗传算法的调度算法,其中染色体编码采用分段编码方式,并提出一种适用于工件工序存在并行性的染色体解码方法.实验结果表明,文中算法能够有效地解决工件工序可并行的作业车间调度问题.     

基于正态云模型的状态转移算法求解多目标柔性作业车间调度问题

为了求解具有多目标多约束的柔性作业车间调度问题,提出一种基于正态云模型的状态转移算法.构建以最小化最大完工时间、机器总负荷及瓶颈机器负荷为目标的多目标柔性作业车间调度问题的数学模型;针对灰熵关联度适应度分配策略在Pareto解比较序列与参考序列之间的差值相等时不能引导算法进化的情况,提出一种改进灰熵关联度的适应度值分配策略;同时引入兼具模糊性和随机性的云模型进化策略以改进状态转移算法,可有效避免算法早熟并增加候选解的多样性.仿真结果表明:基于正态云模型的状态转移算法能够有效解决多目标柔性作业车间调度问题;与其他算法相比,所提出算法求解问题的收敛精度更高、收敛速度更快.     

两阶段流水车间批调度问题的蚁群优化算法

针对差异工件(工件尺寸不同)两阶段流水车间的批处理机调度问题,提出一种以最小化加工时间跨度为目标的蚁群优化算法.根据批中工件在每阶段加工时间的相似程度(标准差衡量),得到一个能够提高批中工件加工时间相似水平的启发式信息.同时,改进蚁群算法的编码方案,并引入局部优化算法来提高优化性能.仿真结果表明,与现有算法相比,该算法在工件规模较大的情况下具有较好的求解性能.     

Research on services encapsulation and virtualization access model of machine for cloud manufacturing

Considering the new requirements of the services encapsulation and virtualization access of manufacturing resources for cloud manufacturing (CMfg), this paper presents a services encapsulation and virtualization access model for manufacturing machine by combining the Internet of Things techniques and cloud computing. Based on this model, some key enabling technologies, such as configuration of sensors, active sensing of real-time manufacturing information, services encapsulation, registration and publishing method are designed. By implementing the proposed services encapsulation and virtualization access model to manufacturing machine, the capability of the machine could be actively perceived, the production process is transparent and can be timely visited, and the virtualized machine could be accessed to CMfg platform through a loose coupling, ‘plug and play’ manner. The proposed model and methods will provide the real-time, accurate, value-added and useful manufacturing information for optimal configuration and scheduling of large-scale manufacturing resources in a CMfg environment.     

Scheduling in a manufacturing shop with sequence-dependent setups

In this paper, the problem of scheduling multiple jobs in a flexible manufacturing cell with multiple machine stations is addressed. Due to the large capital investments that usually characterize flexible manufacturing systems (FMS), an area of control of great interest to system users is that of maximizing the system performance through the minimization of machine idle and setup times. The magnitude of total time spent on machine setups and idle times is influenced by the availability of jobs, job mix, similarities of jobs and job scheduling procedure used. Similar jobs on the same machine require less setup times. Similarly, the use of an adequate scheduling method also reduces total idle and setup times. Such reduction improves the flow times of jobs. In this paper, a heuristic algoritm for scheduling jobs with sequence dependent setup times in a FMS is presented. The measure of performance for evaluating schedule adequacy is the production makespan.     

An anticipative scheduling approach with controllable processing times

In practice, machine schedules are usually subject to disruptions which have to be repaired by reactive scheduling decisions. The most popular predictive approach in project management and machine scheduling literature is to leave idle times (time buffers) in schedules in coping with disruptions, i.e. the resources will be under-utilized. Therefore, preparing initial schedules by considering possible disruption times along with rescheduling objectives is critical for the performance of rescheduling decisions. In this paper, we show that if the processing times are controllable then an anticipative approach can be used to form an initial schedule so that the limited capacity of the production resources are utilized more effectively. To illustrate the anticipative scheduling idea, we consider a non-identical parallel machining environment, where processing times can be controlled at a certain compression cost. When there is a disruption during the execution of the initial schedule, a match-up time strategy is utilized such that a repaired schedule has to catch-up initial schedule at some point in future. This requires changing machine–job assignments and processing times for the rest of the schedule which implies increased manufacturing costs. We show that making anticipative job sequencing decisions, based on failure and repair time distributions and flexibility of jobs, one can repair schedules by incurring less manufacturing cost. Our computational results show that the match-up time strategy is very sensitive to initial schedule and the proposed anticipative scheduling algorithm can be very helpful to reduce rescheduling costs.     

Solving a stochastic single machine problem with initial idle time and quadratic objective

We study a static single machine scheduling problem in which processing times are stochastic, due-dates and penalties for not completing jobs on time are deterministic, and an initial fixed idle time is allowed to be inserted before the processing of the first job begins on the machine. The objective is to determine the optimal sequence and the optimal initial idle time that jointly minimize the expected value of the sum of a quadratic cost function of idle time and the weighted sum of a quadratic function of job lateness. The problem is NP-hard to solve; however, we develop an exact algorithm based on a precedence relation structure among adjacent jobs. Our extensive computational results show that the algorithm can solve large problem instances quickly. We also demonstrate that the proposed problem is general in the sense that its special cases reduce to new stochastic models while its limiting cases simplify to some deterministic models.     

面向司法专题分析的大数据计算资源调度方法

针对司法专题分析过程中面临的交互式分析类数据处理执行效率低的问题,提出了一种基于任务类型的计算资源调度方法,为任务类型建立计算资源配额管理机制。在类型配额内具备抢占式优先调度权,在类型配额外可以借用其他任务类型的空闲资源。实验与分析表明,该方法能够在兼顾普通大数据处理任务执行效率的前提下显著提升交互式分析类任务的执行效率。     

Digital twin-based job shop anomaly detection and dynamic scheduling

Scheduling scheme is one of the critical factors affecting the production efficiency. In the actual production, anomalies will lead to scheduling deviation and influence scheme execution, which makes the traditional job shop scheduling methods are not sufficient to meet the needs of real-time and accuracy. By introducing digital twin (DT), further convergence between physical and virtual space can be achieved, which enormously reinforces real-time performance of job shop scheduling. For flexible job shop, an anomaly detection and dynamic scheduling framework based on DT is proposed in this paper. Previously, a multi-level production process monitoring model is proposed to detect anomaly. Then, a real-time optimization strategy of scheduling scheme based on rolling window mechanism is explored to enforce dynamic scheduling optimization. Finally, the improved grey wolf optimization algorithm is introduced to solve the scheduling problem. Under this framework, it is possible to monitor the deviation between the actual processing state and the planned processing state in real time and effectively reduce the deviation. An equipment manufacturing job shop is taken as a case study to illustrate the effectiveness and advantages of the proposed framework.     

Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals

This paper considers a scheduling problem for a single burn-in oven in the semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. Each job belongs to one of the given number of families. Moreover, the release times of the jobs are different from one another. The objective measure of the problem is the maximum completion time (makespan) of all jobs. A dynamic programming algorithm is proposed in the order of polynomial time complexity for a situation where the number of job families is given (fixed). A computational experiment is performed to compare the time complexity of the proposed algorithm with that of another exact algorithm evaluating all possible job sequences based on batching-dynamic programming (BDP). The results of the experiment show that the proposed algorithm is superior to the other.Scope and purposeThis paper considers a scheduling problem on the burn-in operation in a semiconductor manufacturing process. The burn-in operation is a bottleneck process in the final testing process which is one of four major steps including wafer fabrication, wafer probe, assembly, and final testing steps. Thus, its scheduling is very important to improve the productivity of the whole manufacturing line. The objective of this paper is to find a solution technique that will find the optimal schedule that minimizes makespan for problems which are found in the semiconductor manufacturing industry.     

Service composition model and method in cloud manufacturing

This study optimizes service composition on the basis of task requirements to solve the problem of multitask corresponding multi-service selection. First, the basic path structure and the implementation steps of cloud manufacturing (CMfg) service composition are analyzed, and service composition is divided into four patterns. Second, the quality of service (QoS) index system of service composition is proposed by combining the six goals of time, composability, quality, usability, reliability, and cost; the calculation expressions of QoS under different composition structures are listed; and the mathematical model of CMfg service composition is established. Then, the weight of each index value in QoS evaluation is determined using an improved fuzzy comprehensive evaluation method. Finally, the optimal selection scheme of service composition is proposed by using gray relational analysis method(GM), and the validity of the optimal selection scheme is verified by an example of mold manufacturing.     

Joint optimization of job scheduling and maintenance planning for a two-machine flow shop considering job-dependent operating condition

Two-machine flow shops are widely adopted in manufacturing systems. To minimize the makespan of a sequence of jobs, joint optimization of job scheduling and preventive maintenance (PM) planning has been extensively studied for such systems. In practice, the operating condition (OC) of the two machines usually varies from one job to another because of different processing covariates, which directly affects the machines’ failure rates, PM plans, and expected job completion times. This fact is common in many real systems, but it is often overlooked in the related literature. In this study, we propose a joint decision-making strategy for a two-machine flow shop with resumable jobs. The objective is to minimize the expected makespan by taking into account job-dependent OC. We consider two situations. In the first situation, where the failure rate of a machine under a fixed OC is constant, a hybrid processing time model is proposed to obtain the optimal job sequence based on the Johnson's law. For the second situation, where the failure rate of a machine is time-varying, the job sequence and PM plan are jointly optimized. An enumeration method is adopted to find the optimal job sequence and PM plan for a small-scale problem, and a genetic algorithm-based method is proposed to solve a large-scale problem. Numerical examples are provided to demonstrate the necessity of considering the effect of job-dependent OC and the effectiveness of the proposed method in handing such joint decision-making problems in manufacturing systems.     

基于改进灰狼优化算法的边缘计算任务调度方法

针对边缘计算在离散制造业数据处理过程中存在的时延和资源消耗大的问题,提出了一种基于改进灰狼优化（IGWO）算法的边缘计算任务调度方法。该方法通过对非线性收敛因子以及动态权重的改进,提高了灰狼算法的优化速度和精度,有效降低了终端设备和边缘端的资源损耗以及任务处理的时延。基于不同数据任务量下的处理时延与资源消耗实验,证明了所提模型的有效性,与3种主流任务调度算法相比,数据处理资源消耗和时延最低。将边缘计算任务调度与智能寻优算法相结合并运用到离散制造业,可以提高设备任务的处理速度、降低能耗,为离散制造业智能化转型提供借鉴。