A Note on Single-Machine Lot Scheduling with Splittable Jobs to Minimize the Number of Tardy Jobs

The single-machine lot scheduling problem with splittable jobs to minimize the number of tardy jobs has been showed to be weakly NP-hard in the literature.In this paper,we show that a generalized version of this problem in which jobs have deadlines is strongly NP-hard,and also present the results of some related scheduling problems.

Number of Tardy Jobs of Single Machine Scheduling Problem with Variable Processing Time

The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3 partition problem that if the problem is of ready time and common deadline constrained, its complexity is NP hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.

事件驱动的并行多机模具热处理生产调度

为满足准时交货与节能生产的复合需求,构建了反映加权拖期、炉子装载水平和工件重量偏差程度的优化指标;建立了事件驱动调度机制,对机器完工和任务到达进行实时响应,并通过预测时间窗选取体现前摄性的调度任务集,同时采用"先分后合"的方式解耦工件族间的相互干扰;构造了启发式算法,在每个决策时刻进行滚动求解,基于任务到达时间组批,并用折衷规划计算各工件族的最佳批次,再综合评价确定全局最佳批次。仿真结果表明,与两类常用规则相比,所提方法具有明显的优越性。

随机返工及重加工情形下的Job-Shop调度问题

针对传统Job-Shop数学模型忽略返工及重加工的因素,构建了考虑该情形下的Job-Shop调度数学模型及相应的求解算法。该模型详细分析了返工及重加工的流程,对问题的定义做了进一步推导,模型以总加权拖期最小为目标,并提出一种改进的遗传算法对该模型进行求解。针对该调度情形,对算法中染色体的编码、种群初始化进行改进。种群数据的仿真实验表明,与传统遗传算法相比,改进后的算法在收敛速度、求出的最小总加权拖期方面均优于前者。最后通过对10×10实例调度方案求解及仿真,并与作业车间实际调度结果比较,模型仿真所得总加权拖期小于实际计划调度结果的46%,本模型得出的调度方案是实用且有效的。

求解大规模车间调度问题的一种分解优化算法

针对以最小化加权拖期和为目标的大规模作业车间调度问题,提出了一种基于操作的分解优化算法。该算法采用迭代优化的框架,从原问题对应的操作集合中依次分解出部分操作,并确定其加工顺序。在每一次迭代过程中,首先用模拟退火算法搜索较优的操作分解方案,并形成子问题,然后用遗传算法求解该子问题。针对随机生成的测试问题,以及某减速器厂实际生产数据的计算实验表明,该算法能够在合理的计算时间内获得满意的优化质量。

加工时间和工期一致的单机主次指标排序问题1‖∑U︱T_(max)

本文研究了单机主次指标排序问题1‖∑U︱Tmax。在加工时间和工期具有一致性的情形下,给出了该问题的多项式时间算法。

加工时间服从均匀分布的单机随机排序问题

讨论了工件的加工时间服从均匀分布的单机随机调度问题,目标是使拖后工件数的数学期望最小。采用理论分析的方法,研究了工件的最优加工顺序。结果表明:在(1)工件的权重相等(2)工件的权重与工件的平均加工时间成比例的两种情况下,最短期望加工时间优先规则的不可中断静态优先策略和不可中断动态优先策略是确定使拖后工件数最少的优先策略,并对算法的最优性进行了证明。该成果对非正规目标函数的单机随机排序问题的解决具有一定的参考价值和指导意义。

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

SI Xin ZHENG Yingping AN Xienan ( Institute of Automation,Chinese Academy of Sciences,Beijing 10 0 0 80 )

关于工期分配与加权误工数的双指标排序问题（英文）

排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题.关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式.针对该问题,本文针对约束形式及Pareto优化形式进一步研究了更多的模型.主要结果包括NP-困难性、多项式可解情形以及多项式时间近似方案等结果.通过这些结果,一个多目标优化问题的特征得以完整地刻画.

单机主次指标排序问题(英文)

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax.在同工期且准备时间和工期具有一致性的情形下,给出了该问题的允许中断抢先的多项式时间算法.

一种基于多agent的柔性车间调度系统研究

针对柔性车间调度的特点,提出了一种分布式多agent柔性车间调度系统。系统由工件a-gent,生产单元agent和一个全局agent组成。生产单元agent根据三类agent相互协商得到总评价指数选择工件,工件agent根据特定规则选择加工设备进行加工。最后用Arena仿真软件建立模型,对柔性车间调度加权滞后和问题进行仿真实验,与传统的分派规则比较,结果显示基于多agent的柔性车间调度方法明显优于传统的分派规则。

成组加工中的加工全程和延误工件数问题

本文在同组工件连续加工的条件下考虑了单机加工中的二个排序问题,其目标函数分别为极小加工全程和延误工件数。文中在不同的条件下对它们给出了多项式时间算法。

单机分族分批排序的最小误工个数问题

文章研究了同一族内,给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O(mb(n/m)2m)的动态规划算法。

带有交货期的多阶段流水作业排序

很多生产加工企业需要按预定交货期来安排柔性流水作业的生产,本文研究带有交货期的多阶段流水作业排序问题,以最小化误工成本为优化目标,利用改进的明显误工成本作为优先因子完成第一阶段排序,再采用先到先服务的规则对后续阶段排序。算法能解决三个及更多阶段的作业排序问题,实例应用表明了算法的有效性。

带机器故障的两台机带权误工数排序问题

讨论机器带故障中断的两台平行机排序问题,工件加工时间均为单位时间,目标是极小化带权误工工件数.当转移时间t=0时给出了最优的算法.当t≠0时,给出了一个多项式时间的近似算法,并证明算法解与最优解至多相差一个带权误工数.

最小化加权误工工件数的多代理平行分批排序(英文)

考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.

拖后工件数最少的单机随机调度问题

讨论了工件准备时间、加工时间和交货期都为随机变量的单机调度问题．文中对拖后工件采用了另一定义方法．在此基础上，对于（1）工件的加工时间和交货期分别可随机排序而准备时间独立同分布、（2）工件的准备时间和交货期可随机排序而加工时间独立同分布的情况给出了确定使拖后工件数最少的最优排序算法并对算法的最优性进行了证明．

随机加工时间的单机随机调度问题

讨论了加工时间服从均匀分布的单机随机调度问题,目标是使拖后工件数的数学期望最小.采用理论分析的方法,给出了期望加权误工任务数的表达式,研究了工件的最优加工顺序.结果表明:在工件的权重和工件的平均加工时间不成比例的最一般的情况下,最短加工时间和最长加工时间优先规则的联合使用给出了使拖后工件数最少的优先策略,并对算法的最优性进行了证明.该成果对于非正规目标函数的单机随机排序问题的解决具有一定的参考价值和指导意义.

带固定工件的单机排序问题1|FB,r_j,pmtn|Σ_jU_j的多项式算法(英文)

研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,r_j,pmtn|∑_jU_j.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n^4+mlog m),其中m和n分别是固定工件数和自由工件数.

机器随机故障时使拖后工件数最少的单机调度问题

本文讨论了机器随机故障时，使拖后工件数最少的单机调度问题．结果表明，确定情况下的Moore－Hodgson算法，在机器随机故障时，能以概率1确定最优工件排序．