三台平行机排序的一个复合半在线问题的算法

本文讨论一个三台平行机半在线排序问题.对预先知道工件的总加工时间和最大的工件的加工时间的复合半在线模型,我们证明了不存在半在线算法,其竞争比为4/3,并给出了一个竞争比为7/5的半在线算法,两者的差距小于0.067.     

考虑共享机器租借费用的在线订单加工策略及竞争分析

探究了拥有两台平行机资源的制造商在共享制造环境下的实时加工调度决策问题。结合租赁外部共享机器的固定成本与可变成本因素，运用在线理论与竞争分析方法构建了平行机调度over-list在线模型，其最小化目标是工件总完工时间与机器租赁总成本之和。针对工件均为单位长度的情形，分析了问题离线最优方案，进而证明了竞争比下界为■,其中，a为固定租赁成本系数，b(0≤b+时，该下界趋于4/3;同时，设计给出了在线策略TS,并证明当a=2时该策略竞争比为4/3;当a≥3时，其竞争比为1.89。     

大规模集成电路预烧作业中分批排序问题的数学模型

分批排序(Batch Scheduling)是在半导体生产过程的最后阶段提炼出来的一类重要的排序问题。单机分批排序问题就是n个工件在一台机器上加工,要将工件分批,每批最多可以同时加工B个工件,每批的加工时间等于此批工件中的最大的加工时间。Skutella^[8]1998年把平行机排序的P｜｜∑ω_jC_j和R｜｜∑ω_jC_j表述成二次的0-1整数规划,得到一些令人满意的结果;国内罗守成等^[9]、张倩^[10]给出了单机排序问题1｜｜∑ω_jC_j的数学规划表示,对于用数学规划来研究排序问题是一个很有意义的进展。本文首先介绍总完工时间和最小的带权单机分批排序问题1｜B｜∑ω_jC_j,然后将1｜B｜∑ω_jC_j表示成数学规划的形式,并且用数学规划中的对偶理论证明了SPT序是其特殊情况1｜B=1｜∑C_j的最优解。     

考虑加工与运输协同调度的单机排序问题

在考虑加工与运输协同调度的单机排序问题中,每个工件尺寸不同,工件在一台机器加工后,由m辆有容量限制的运输工具运送到同一个顾客处,目标是极小化最后一个送到其顾客的工件的到达时间,本文给出了该问题的一个最优算法,并且证明了该算法的最坏情况界为3/2。     

面向成套订单问题的工艺规划与排序的集成研究

本文从工艺规划与排序的集成优化角度研究了成套订单问题^[1],克服了单独研究工艺规划和排序局部优化的局限性.文章中考虑了同一工件内部各道工序之间存在的优先加工限制,以及工件在不同机器上加工需要转移时间和工序间接连加工需要机器调整时间的情况,建立了成套订单问题的集成排序模型,并提出了针对求解大规模问题的基于遗传算法的启发式算法,最后通过一个算例对所研究的集成排序问题和所提出的算法进行了说明,计算结果表明了算法的有效性.     

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。     

考虑学习率和搬运时间的人工作业系统生产过程时间组织与优化

在同时考虑员工学习率和运输工序时间的基础上,对该类型人工工序作业系统的批量加工模式生产周期模型及优化问题进行研究。给出批量工件以不同移动方式完成加工的生产周期形式,并详细地对该研究背景下的批量工件以平行顺序移动方式完成加工的生产周期模型进行理论证明。在给定算例的基础上,对仅考虑搬运时间、考虑学习率和搬运时间等两种情况的生产周期进行对比分析。最后,在详细分析工艺工序时间、员工学习率、运输工序时间、增加峰工艺工序员工人数等优化措施对批量工件生产周期优化效果影响的基础上,提出针对不同移动方式完成加工的批量工件进行生产周期优化的策略,为该类型制造系统正确进行现场改善提供可以借鉴的准则。     

目标函数为∑和max的双目标最短路问题:算法和复杂性

本文研究了一个双目标最短路问题。在该问题中,一个目标函数是∑形式,另一个目标函数是max形式。首先给出了一个时间复杂性为O(m²logn)的算法产生代表有效解集合。然后研究了∑和max的组合目标函数最短路问题,对动态问题和静态问题,分别给出了一个时间复杂性都为O(m²logn)的算法。最后在字典序最优解的意义下,本文给出了两个时间复杂性都为O(mlogn)的算法。     

基于微粒群算法的单机不同尺寸工件批调度问题求解

提出了一种改进的具有全局搜索能力的微粒群算法,对工件尺寸有差异的单机批调度问题的制造跨度进行优化。针对问题中工件尺寸不同且分批加工的特点,设计了微粒的编码方式;对进化过程中产生的极优解,采用了混沌优化策略进行改进,避免早熟收敛的问题。仿真实验结果表明,本文算法的时间性能和近似解质量均优于现有的其他方法。     

加工能力受限的单机干扰管理研究

针对单机环境下最小化加权折扣加工时间和的排序问题,研究如何应对可预见的干扰事件。由于干扰事件使得机器加工能力受限,初始最优加工时间表不再可行,采用外包的方式来进行干扰管理。构建了排序模型,同时考虑原目标和与初始计划偏离的扰动目标,选择外包工件集并对所有工件进行重排序。为了求解得到的双目标排序问题,基于理想点法设计了一种动态规划算法和量子遗传算法相结合的算法。最后通过一个数值算例说明,该排序模型对于求解加工能力受限的单机干扰管理问题是有效的。     

Machine Pacing and Shiftwork

Machine-paced work and shiftwork are highly prevalent working conditions commonly believed to have adverse individual and organizational consequences. This article examines the empirical evidence for such effects, and acknowledges the conceptual and methodological problems which have clearly plagued pacing and shiftwork researchers. The literature on pacing while suggestive of overall health and performance effects indicates that the magnitude of such effects are in all likelihood situationally and invididually determined. Very little is known, however, about such interactions. Similarly, the shiftwork literature is contradictory and inconclusive. Shiftwork appears to affect both the quality and quantity of sleep and to disrupt a wide range of physiological and behavioral circadian rhythms. The long-term consequences of these effects are still not known.     

Preemptive Machine Covering on Parallel Machines

This paper investigates the preemptive parallel machine scheduling to maximize the minimum machine completion time. We first show the off-line version can be solved in O(mn) time for general m-uniform-machine case. Then we study the on-line version. We show that any randomized on-line algorithm must have a competitive ratio m for m-uniform-machine case and ∑_{i = 1}^m1/i for m-identical-machine case. Lastly, we focus on two-uniform-machine case. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the on-line problem for every machine speed ratio s≥ 1. We further consider the case that idle time is allowed to be introduced in the procedure of assigning jobs and the objective becomes to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the problem for every s≥ 1. We show that randomization does not help.     

On the Robust Single Machine Scheduling Problem

The single machine scheduling problem with sum of completion times criterion (SS) can be solved easily by the Shortest Processing Time (SPT) rule. In the case of significant uncertainty of the processing times, a robustness approach is appropriate. In this paper, we show that the robust version of the (SS) problem is NP-complete even for very restricted cases. We present an algorithm for finding optimal solutions for the robust (SS) problem using dynamic programming. We also provide two polynomial time heuristics and demonstrate their effectiveness.     

呼唤干部考察的"X光机"

干部考察是了解干部情况的重要途径,是选拔任用干部的必经程序,各级党委和组织人事部门十分重视干部考察工作.江泽民总书记最近指出,干部考核要能像X光机那样快速准确地了解评价干部.他对干部考核考察工作提出了很高的要求.但是,干部考察工作目前还存在一些令人不够满意的地方,考察失实失真问题依然存在,严重影响了干部选拔任用工作的正常开展.那么,当前干部考察工作中到底存在一些什么问题,又该如何解决,如何造出把干部认识清、考察准、考察透的"X光机"呢?     

考虑机器间替代性的制造单元柔性度量

本文在假定柔性制造单元中的各台机器能够以不同效率实现任务的替代加工的基础上,建立了包含时间和成本的效率矩阵,综合考虑任务出现的概率、每台机器可加工的任务数量、任务在机器间一次指派和二次指派的概率以及任务在机器间的替代比例和替代概率等困扰实际生产因素的制造单元的柔性度量方法.最后,结合算例对该方法的应用过程进行了分析.     

基于机器学习的企业定价算法研究

本文根据经济微观仿真模型ASPEN的定价机理,提出了一种自动学习算法.该算法借鉴分类器系统中的规则及消息系统和信任分配系统,模拟了企业通过渐进学习得到最大利润下的价格的过程.文中以一个简单经济模型中的两个企业代理人的价值竞争为例,将算法的定价与理论计算法的结果进行了比较,比较结果表明该算法很好地实现了企业定价的自动学习.     

安装时间与次序相关的生产调度干扰管理研究

在安装时间和次序相关的单机调度问题中,为应对突发性的工件优先级变动造成的影响,构建了双目标重调度模型。原目标为生产的流程时间,扰动目标为工件的加工次序扰动。针对模型中的双目标,设计了基于有效解的两阶段混合启发式算法进行求解,在原目标和扰动目标之间进行权衡。混合算法第一阶段里,基于任意单个工件次序变化将双目标问题转化成单目标TSP问题,利用最近邻域和插入混合求得单目标问题的若干解,构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势,对初始种群进行扩展搜索,最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标,验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。     

基于局部性修复的HFS机器故障重调度

针对机器故障下的HFS重调度问题,提出了重调度前后调度方案在时间安排和机器指派上的一致性度量方法,从约束变化的角度建立其动态约束满足模型。模型能够反映工件对重调度前后调度方案的一致性具有不同要求的实际情况。针对问题的模型及其特点,提出了基于局部性修复的重调度算法。仿真实验表明,本文提出的模型和算法是有效的。     

Flow Shop Scheduling Problems Under Machine–Dependent Precedence Constraints

The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.