考虑多个RMAs的单机调度问题

在处理时间不断恶化的情况下,针对插入多个机器维护阶段(RMAs)和考虑交货期安排的单机调度问题展开研究,目标是最小化提前和拖期惩罚。产品加工过程中,在处理工件之前插入多个RMAs可以降低恶化现象从而恢复机器的生产效率,目的是同时找到最优序列、最优松弛时间和RMAs的最优位置以使提前和拖期惩罚最小。根据问题的特点,提出了相关的性质和定理,通过证明得出了最优的松弛时间。最后,证明了该问题在多项式时间内是可解的。     

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

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

批处理机上具有两类释放时间的工件集竞争调度问题

研究了两个工件集合竞争在一台批处理机上加工的调度问题, 其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批, 每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小, 针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间, 使得另一个集合工件的最大完工时间不超过给定上界问题, 分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间, 使得另一个集合工件的最大完工时间不超过给定上界问题, 证明为一般意义NP--!难问题, 并给出伪多项式时间最优求解方法.     

具有恶化效应和学习效应的单机成组调度问题

讨论了一类具有恶化效应和学习效应的单机成组调度问题, 其中工件的加工时间为开工时间和组内工序的函数. 通过对问题性质的分析以及多项式时间算法的描述, 得出如下结论: 在单机成组调度问题中, 即便工件的加工时间同时受恶化效应和学习效应的制约, 极小化完工时间问题以及极小化总资源消耗的问题仍是多项式时间可解的.     

最小化误工工件个数的两代理单机排序问题

针对研究了两代理情形下的单机排序问题,考虑两类问题：一是在误工工件个数不超过一个给定值的情况下使得总误工最小,另一个是代理[A]的工件加工时间和权重满足反一致关系时,在误工工件个数不超过一个给定值的情况下使得总加权完工时间之和最小。对于这两类问题采用动态规划方法分别给出最优性质和相应的拟多项式时间算法。     

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

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

一类线性加工时间单机调度问题

讨论一类线性加工时间单机调度问题.在这类问题中,工件具有相同的基本加工时间,但每个工件的实际加工时间以其开工时间线性增长.对满足无延迟工件条件下极小化提前惩罚和问题,满足最大完工时间限制条件下极小化资源消耗总量的问题和满足资源消耗总量限制条件下极小化最大完工时间的问题,分别给出了最优算法.     

带线性恶化工件的零等待流水车间调度

研究了以最小化总加权完成时间为目标的带线性恶化工件的零等待流水车间调度,其中工件的加工时间表示为开始时间的线性恶化函数,每个工件在不同机器有各自的恶化率.为了对该问题进行求解,提出了一种融合CDS启发式算法、局部搜索和自适应遗传算法的混合启发式算法.引入CDS启发式算法改善初始工件加工序列群,设计遗传参数自适应更新策略...     

动态自适应加权多态蚁群算法求解差异工件单机批调度问题*

针对差异工件的单机批调度问题,提出了动态自适应加权多态蚁群算法对最大完工时间进行优化,该算法引入了不同种类的蚁群,每种蚁群都有不同的信息素调控机制,并根据批调度问题对不同种类的蚁群的状态转移概率和信息素更新机制进行了改进,同时将局域搜索与全局搜索相结合,从而更符合蚁群的真实信息处理机制。对不同规模的算例进行了仿真,结果验证了该算法的有效性和可行性。     

GA/LP算法求解带组换装时间的单机调度问题

以包头某钢铁线材企业实际调度问题为背景,针对带组换装时间的单机提前/拖期调度问题,建立了混合整数线性规划模型.根据模型的特点,将该问题的求解分为最优排序变量的确定和最优开工时间的确定两个层次.由于该问题是NP难的,提出了一种基于遗传算法和线性规划相结合的GA/LP算法.在算法中,利用GA在外层搜索遍历二元变量空间来优化工件排序;在内层则利用LP来确定满足约束条件的最优连续解.为了提高算法寻优性能,降低算法运行时间,提出了一种基于问题特征的种群初始化方法.最后,针对三种交叉算子在随机问题上进行了测试,实验结果表明,该算法能够有效求解问题.     

Single machine due-date scheduling of jobs with decreasing start-time dependent processing times

We study the problem of scheduling jobs whose processing times are decreasing functions of their starting times. We consider the case of a single machine and a common decreasing rate for the processing times. The problem is to determine an optimal combination of the due date and schedule so as to minimize the sum of due date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.     

A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.     

考虑能耗与工时恶化作用下的并行机调度优化

在热处理加工环境中,工件温度随着其开工时刻的延误不断下降,为了能够正常加工不得不保温或重新加热.针对这一现象,本文考虑了能耗与工时恶化作用下的并行机调度问题,以最小化总拖期和能耗为目标构建了混合整数规划模型.由于问题的复杂性,提出了一种遗传变搜索算法,其通过遗传操作获得变邻域搜索操作的解集,而后使用变邻域结构进行寻优操作.算例测试表明：较之传统遗传算法以及数学规划器Gurobi的计算结果,所提出的算法可以有效减少综合能耗和拖期成本.     

一种有到达时问的多处理器混合流水车间调度的遗传算法

有到达时间的多处理器混合流水车间调度问题在实时机器视觉系统等领域有广泛的应用.这一问题是NP-困难的.鉴于以上原因,给出一种遗传算法.对不同的交叉算子和变异算子以及涉及的参数的不同取值进行试验,并对试验的结果进行分析和讨论,从而给出最好的参数组合.     

Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

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

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

混合优先约束下带模糊交货期的单机调度问题的研究

讨论了一类模糊交货期和混合优先约束下的单机调度问题．模糊交货期表示对任务完成时间的满意程度；混合优先约束包括普通优先关系和模糊优先关系，模糊优先关系反映了对任务间优先次序的满意程度．调度的目的是同时最大化模糊交货期和混合优先约束的最小满意程度．对于上述双目标函数调度问题，通过搜索非支配解，得到最优调度．