具有线性恶化加工时间的调度问题

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性 函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费 用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用 Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则 Flowshop问题可以转化为单机问题.     

单机调度中平均流程时间和延期工件数的双目标问题

1 引言 本文在具有平均流程时间和延期工件数两个目标的情况下对单机多目标问题进行研究,所研究的调度环境为假设工件集N的n个工件在一台机器上进行无中断的加工,每个工件的加工时间、到达时间和交工日期分别为pi,ri和di,且每个工件在零时刻到达,即ri=0,其完工时间为Ci,流程时间Fi=Ci-ri=Ci,平均流程时间(F)=n∑i=1Fi/n.     

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

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

基于改进遗传算法的单机成组作业调度

提出了单机成组作业调度的改进遗传算法。优化目标为总流程时间的单机成组作业调度问题明显是NP-hard问题,此问题的多项式求解方法不能求取最优解,而一些启发式算法也只能求出此问题的次优解。为获得单机成组作业最优调度,通过采用整数实值编码,随机采样选择,单点交叉以及变异检查,设计了单机成组作业调度的改进遗传算法。仿真结果表明,算法能够找到此问题的最优解,其性能优于加权最短加工时间(WSPT)启发式算法。改进遗传算法能够灵活解决各种单目标调度及多目标调度问题。     

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

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

面向多机动态调度问题的两层Q学习算法

对于单机动态调度问题十分有效的Q学习,在多机动态调度环境下却由于缺乏全局眼光而效果欠佳,因此提出了一种双层Q学习算法．底层Q学习着眼于局部,以最小化设备空闲和作业平均流经时间为目标,学习单机调度策略;而顶层Q学习则着眼于全局,以平衡机器负载、最小化整体拖期值为目标,学习如何分配作业到合适机器．文中分别给出了两层Q学习的动作集、状态空间划分方式和奖惩函数设计,并通过对多机动态调度问题的仿真实验表明,提出的双层Q学习能够很好地解决改善动态环境下多机调度问题．     

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

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

释放时间和工期同序的单机连续型批调度问题

本文研究的连续型批处理机调度问题, 是在钢铁工业管坯的加热过程中提出来的. 工件带有释放时间和工期, 工件进入和离开机器是按周期依次进行的. 本文针对单机连续型批调度问题中工件释放时间和工期同序的情况, 分析了极小化最大拖期和拖期工件数等问题的计算复杂性, 证明了两类问题都是强NP-难的. 对于工件的释放时间和加工时间、工期都同序的特殊情况, 分别给出了能够获得对应问题的最优解的多项式算法.     

基于工件窗口的发动机装配车间滚动调度

针对航空发动机装配车间因订单变更,机器故障等随机扰动造成静态调度结果失效问题,建立了重入式混合车间FIow－shop动态调度模型,综合考虑了机器,班组能力等多种资源约束;提出了一种基于工件窗口的滚动调度方法,从滚动窗口的确定,滚动机制,滚动窗口内部算法三个方面提高动态调度性能,实验表明该方法可行有效。     

关于ω—正则语言类的一个子类的特征

为了给出本文的主要结果,首先引进了由有穷字母表∑上的ω~-语言所确定的集合∑~ω上的ω-Nerode等价关系的概念.在此基础上证明了∑上的与前缀逆相关的ω~-语言是ω~-正则语言,当且仅当由它所确定的ω-Nerode等价关系的指数有穷.从而,本文从代数、集合的角度给出了在∑上的与前缀逆相关的一类ω~-语言中,ω~-正则语言的特征.     

Further properties of optimal hedging points in a class ofmanufacturing systems

For single-part-type manufacturing systems with homogeneous irreducible Markov machine failure rates, it is known that simple feedback control policies, called hedging point policies, are optimal, and the stationary probability distribution of the part surplus can be obtained analytically for given tentative values of hedging points. In this paper, the authors extend previous work on the ordering of optimal hedging points, and some better results are obtained     

Optimal PHP production of multiple part-types on a failure-pronemachine with quadratic buffer costs

We consider a single, failure-prone machine, producing multiple part-types The objective is to minimize the expected sum of quadratic buffer costs. In general, the optimal solution to this problem is unknown. However, by restricting the allowable set of control policies to the class of prioritized hedging point (PHP) policies, we are able to determine simple, analytical expressions for the optimal hedging points. We also provide some results for choosing the optimal priority ordering     

Enhanced dynamic programming algorithms for series line optimization

Dynamic programming value iteration is made more efficient on a five-machine unreliable series line by characterizing the transient and "insensitive" states. Holding costs are minimized subject to a service level constraint in a make-to-stock system with backordering. State-space truncations are chosen by checking the recurrent class in previous runs. An approximate model is developed that reduces the number of machine states. Monotone control theory is used to restrict the search for a control switching surface. Numerical optimal policies are compared with the heuristic control point policy and several characteristics of optimal policies are identified.     

Determination of an optimal configuration of operating policies for direct-input-output manufacturing systems using the Taguchi method

Some modern manufacturing systems have workstations directly integrated with a centralized storage and handling system for work-in-process. We consider a Direct-Inlet-Output manufacturing system(DIOMS) which has a number of machine centers placed along a built-in automated storagejretrieval system(AS/RS). The storagdretrievai(S/R) machine handles parts placed on pallets for the machine centers located at either one or both sides of the AS/RS.

This paper investigates the operational aspect of DIOMS by the Taguchi method. Four operating policies including input sequencing control. dispatching rule for the S/R machine, machine center-based part type selection rule, and storage assignment policy are treated as design factors. For the performance characteristics, man flow time and throughput are adopted. The number of machine centers, the number of part types, demand rate, processing time and the rate of each part type. vertical and horizontal speed of the SIR machM and the size of a local buffer in the machine centers are considered as noise factors in generating various DIOMS environments. A robust design experiment with inner and outer orthogonal arrays are conducted by computer simulation, and an optimal configuration of operating policies is presented which consists of a combination of the level of each design factor. The validity of the optimal configuration is investigated by comparing its SN ratios with those obtained by an experiment with fiill factorial designs.     

Scheduling one-part-type serial manufacturing system under periodic demand: a solvable case

The paper studies one-part type, multiple-stage production system with periodic demands. A buffer of infinite capacity is placed after each machine. Inventory flow through buffers is controlled by machine production rates. The objective is to find a cyclic production rate, which minimizes all inventory-related expenses over an infinite planning horizon. With the aid of the maximum principle, optimal production policies are derived and the continuous-time scheduling problem is reduced to a discrete timing problem. As a result, a polynomial-time algorithm is suggested to calculate the optimal production rate. A numerical example is used to illustrate the algorithm.Scope and purposeNumerical and heuristic approaches have been suggested for production control of automated-serial-manufacturing systems. These approaches try to derive production control policies that would minimize overall costs related to inventory, backlog, and production. The quality of these approaches is often difficult to assess, and they can be time-consuming to implement. Therefore, increasing attention has been directed to optimal control policies of production systems that can be derived precisely and quickly. This paper addresses a special case of the production system manufacturing a single product type to meet a periodic demand. Given a certain assumption on cost relationship, we derive a fast and simple scheduling algorithm that calculates the optimal policy.     

基于M-Petri网的活性研究

文章给出了M－Petri网的概念,并对其活性进行分析,给出了几个判定 M－Petri网活的条件。     

The impact of OPT and TPM on the economic production quantity

In manufacturing systems, the material flow is influenced by a number of factors, such as batching policies, capacity of machines, machine breakdowns, etc. Realizing the role of batching policies and reliability of machines in production systems, a mathematical model is presented here for determining optimal batching policies with the objective of improving the speed of material flow considering machine breakdowns and batch splitting and forming. This model is employed for studying (i) the significance of total preventive maintenance (TPM); (ii) the use of the optimized production technology (OPT) concept in batching policies; and (iii) the influence of a set-up cost reduction programme on the performance of manufacturing systems. The basic criterion considered for optimizing the batch sizes is the minimization of total system cost (TSC). An example problem is solved to explain the application of the model.     

Stochastic scheduling problems with general position-based learning effects and stochastic breakdowns

The focus of this study is to analyze position-based learning effects in single-machine stochastic scheduling problems. The optimal permutation policies for the stochastic scheduling problems with and without machine breakdowns are examined, where the performance measures are the expectation and variance of the makespan, the expected total completion time, the expected total weighted completion time, the expected weighted sum of the discounted completion times, the maximum lateness and the maximum tardiness.     

Self-Monitoring Machines and anωHierarchy of Loops

An ordinal hierarchy of recursive functions is developed based on the level to which a function requires a machine computing it to monitor and make decisions concerning itself. The major theorem states that the functions with self-monitoring level belowω^ωare precisely the class of loop functions (or primitive recursive functions).     

Modelling the startup of machine tools for energy efficient multi-sleep control policies

Energy efficient control strategies have been of recent interest in literature as promising measures to reduce the energy consumed by production equipment during interruptions of part flow. A general time-based control policy is analyzed. Machine idle times are assumed stochastic and the expected value of the energy consumed per produced part is reduced while assuring a certain target of expected production rate. The startup time required to resume the service depends on the time period the machine stays in a low power consumption state. Since the startup is often related to one or more machine components, the optimal policy might be to partially switch the machine. Therefore, a policy acting at component level is also analyzed where the duration of the startup depends on the set of machine components that are switched off. The policy is compared to state-of-the-art policies and discussed for a set of simulated numerical cases representing several production environments.