关于误工的两个代理单机排序问题 被引量：4

1

作者 张新功 陈秋宏 王祥兵 《重庆师范大学学报（自然科学版）》 CAS CSCD 北大核心 2018年第4期1-6,共6页

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定... 【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。 展开更多

关键词 总误工 两个代理 一致性 最大误工

原文传递

精确动态规划算法求解绿色单机调度问题 被引量：4

2

作者 杨嫒 钱斌 +2 位作者 胡蓉 祝晓红 向凤红 《控制与决策》 EI CSCD 北大核心 2021年第8期1891-1900,共10页

针对一类生产实际中广泛存在的绿色单机调度问题,即带释放时间的低碳单机调度问题,提出一种精确动态规划算法(exact dynamic programming algorithm,EDPA)进行求解,优化的主要和次要目标分别为最小化最大延迟时间和总碳排放量.首先,建... 针对一类生产实际中广泛存在的绿色单机调度问题,即带释放时间的低碳单机调度问题,提出一种精确动态规划算法(exact dynamic programming algorithm,EDPA)进行求解,优化的主要和次要目标分别为最小化最大延迟时间和总碳排放量.首先,建立问题的排序模型,该模型可用三元法表示为1|agr(rj,dj)|TCE/Tmax,属于NPhard问题;其次,通过分析排序模型的性质,提出基于工件排序和机器状态选择的交货期最早优先规则(earliest due date,EDD),可确保得到问题最优解;再次,根据所提出规则构建状态递推方程,进而基于该方程设计可对问题解空间执行状态树搜索的EDPA,该算法为具有伪多项式时间的精确算法,可以获取问题的最优解;最后,通过在测试问题和企业实例上的仿真实验,验证所提出算法不仅可以最小化最大延迟时间,而且还能有效地减少总碳排放量. 展开更多

关键词 单机调度问题 最大延迟时间 碳排放 动态规划

原文传递

具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案 被引量：3

3

作者 金苗苗 吴蒙洁 罗文昌 《运筹与管理》 CSSCI CSCD 北大核心 2021年第8期87-92,共6页

本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个... 本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个工件的完工时间已确定每个工件的承诺交付时间。然而,在工件正式开始加工前,原计划用于加工的某段时间区间因临时用于检修机器而导致机器在该时间区间不再可用,需要对工件重新排序。为了确保在新的重新排序中,工件的延误成本不致太大,决策者可以选择拒绝部分工件,但需支付相应的拒绝费用。任务是确定接受工件集和拒绝工件集,并将接受的工件在考虑机器具有不可用区间的条件下重新排序使得接受工件集的总加权完工时间,总拒绝费用及赋权最大延误之和最小。该问题是NP-困难的,对此给出了伪多项式时间动态规划精确算法,利用稀疏技术设计了完全多项式时间近似方案。 展开更多

关键词 重新排序 不可用区间 拒绝 最大延误 近似方案

下载PDF 职称材料

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

4

作者 孙玉芹 原晋江 《运筹与管理》 CSCD 2004年第5期26-30,共5页

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

关键词 排序 主次指标 最大误时 误时工件数 P问题

下载PDF 职称材料

序列相关Setup单机调度的最小化最大拖期分枝定界算法

5

作者 罗小川 刘长勇 +1 位作者 刘晓 王成恩 《东北大学学报（自然科学版）》 EI CAS CSCD 北大核心 2005年第10期938-941,共4页

研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反... 研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性. 展开更多

关键词 序列相关Setup 交货期 最大拖期 单机调度 分枝定界

下载PDF 职称材料

单机主次指标排序问题1｜｜Tmax｜∑Uj的P子问题

6

作者 孙玉芹 刘建军 《新乡师范高等专科学校学报》 2006年第5期1-4,共4页

研究了单机主次指标排序问题1｜｜Tmax｜∑Uj。在工件LPT序与EDD序一致的情形下，给出了该问题的一个多项式时间可解的子问题。

关键词 排序 主次指标 最大误时 误时工件数 单机 P子问题 组合数学

下载PDF 职称材料

单机主次指标排序问题(英文) 被引量：1

7

作者 孙玉芹 原晋江 《运筹学学报》 CSCD 北大核心 2005年第2期63-67,共5页

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

关键词 排序问题 指标 单机 PM 多项式时间算法 准备时间 一致性 工期

下载PDF 职称材料

平行机的最大延误问题

8

作者 霍录景 《价值工程》 2015年第2期308-309,共2页

文章研究了一种具有准备时间的平行机调度问题,目标函数是最大延误,对相关的模型给出了算法,并通过实例验证。

关键词 平行机 最大延误 准备时间

下载PDF 职称材料

有分离调整和移走时间的两机器流水作业最大延误问题

9

作者 陈秀宏 《淮阴师范学院学报（自然科学版）》 CAS 2003年第2期87-90,共4页

在工件的调整时间和移走时间独立于加工时间的两机器流水作业问题中,同一工件的 调整"步及 移走 "步在两台机器上可重叠进行,但 加工"步不能重叠.本文以最大延误为目标函数讨论问题的解中工件排列应满足的条件,根据这些... 在工件的调整时间和移走时间独立于加工时间的两机器流水作业问题中,同一工件的 调整"步及 移走 "步在两台机器上可重叠进行,但 加工"步不能重叠.本文以最大延误为目标函数讨论问题的解中工件排列应满足的条件,根据这些条件我们构作了两个近似算法. 展开更多

关键词 两机器流水作业 最大延误 调整时间 移走时间 加工时间 近似算法 目标函数

下载PDF 职称材料

有分离的调整和移走时间的三台机流水作业问题

10

作者 王磊 陈秀宏 孟炜 《沈阳理工大学学报》 CAS 2007年第6期84-87,共4页

以最小化最大延误为目标函数,讨论了三台机器的流水作业问题,其中每个工件的操作由"调整"步、"加工"步以及"移走"步组成,而工件的调整和移走时间都与加工时间相分离,同一个工件的"调整"步和&qu... 以最小化最大延误为目标函数,讨论了三台机器的流水作业问题,其中每个工件的操作由"调整"步、"加工"步以及"移走"步组成,而工件的调整和移走时间都与加工时间相分离,同一个工件的"调整"步和"移走"步在三台机器上可以重叠,但"加工"步不能重叠,并且第一台机器上没有空闲时间,工件一旦开始加工就不允许中断.给出了该问题的一些支配关系,并由此构造了一个近似算法. 展开更多

关键词 流水作业 调整时间 加工时间 移走时间 最大延误 近似算法

下载PDF 职称材料

单机序列相关Setup最小化最大拖期算法

11

作者 罗小川 王成恩 《计算机应用》 CSCD 北大核心 2005年第8期1829-1832,共4页

研究了一个具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期。提出了一个求解该问题的分枝定界枚举算法,其中包括确定问题上界和下界的方法,以及两条优势规则。计算实验证明了本文提出算法的有效性。

关键词 序列相关Setup 交货期 最大拖期 分枝定界 单机调度

下载PDF 职称材料

一种受限于给定最大延误上界的单目标启发式算法

12

作者 池淑珍 周春光 +1 位作者 张长胜 杨草原 《吉林大学学报（理学版）》 CAS CSCD 北大核心 2010年第5期805-810,共6页

基于有效求解在未超过给定的最大延误上界这一约束条件下最小化总完工时间的置换流水车间调度问题,提出一种新的迭代贪心启发式算法IG_CZ,通过结合全局和局部优化策略获得最优解或近似最优解.并在Taillard基准测试集上对不同规模的问题... 基于有效求解在未超过给定的最大延误上界这一约束条件下最小化总完工时间的置换流水车间调度问题,提出一种新的迭代贪心启发式算法IG_CZ,通过结合全局和局部优化策略获得最优解或近似最优解.并在Taillard基准测试集上对不同规模的问题进行算法性能测试,实验结果表明,IG_CZ算法不仅简单、易于实现,而且求解能力及解的质量优于对比的其他算法。 展开更多

关键词 流水车间调度 迭代贪心 完工时间 最大延误

下载PDF 职称材料

目标函数是最大延误的数学期望的单机随机调度问题 被引量：2

13

作者 薛瑞红 李扬 《科学技术与工程》 2007年第21期5643-5644,共2页

在任务的加工时间和工期是相互独立的随机变量的情况下研究单机随机排序问题,目标函数为最大延误的数学期望。通过理论分析,给出了该问题的不可中断静态优先策略,并通过实例验证。

关键词 单机 随机排序 最大延误 优先策略

下载PDF 职称材料