共查询到19条相似文献,搜索用时 500 毫秒
1.
本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界. 相似文献
2.
讨论工件加工时间是等待时间的非线性增加函数的单机排序问题,目标函数为极小化完工时间和与极小化最大延误.基于对问题的分析,对于一般非线性函数的情况,给出了工件间的优势关系.对于某些特殊情况,利用工件间的优势关系得到了求解最优排序的多项式算法.推广了文献中的结论. 相似文献
3.
研究了具有线性恶化工件的单机排序问题,其中线性恶化工件指的是工件的加工时间是开工时间的线性增长函数.在一般情况下,对目标函数为极小化完工时间平方和与极小化总误工数问题分别给出了最优算法.此外,在分段情况下,对目标函数为极小化最大完工时间问题也给出了最优算法. 相似文献
4.
讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法. 相似文献
5.
考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法. 相似文献
6.
7.
杨晓坡 《数学的实践与认识》2008,38(22)
讨论具有连续资源的单机排序问题.在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数.考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量.第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间.对两类问题讨论了最优排序的某些特征.基于对问题的分析,分别给出了求解最优资源分配的方法.结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立. 相似文献
8.
曾相戈 《数学的实践与认识》2006,36(4):144-150
提出了一种快速而有效的启发式规则(fam ily slack,简称FSLACK),来求解极小化总延误时间和极小化最大完工时间两个目标,工件按产品类型成组,带模具数量约束的平行机器生产调度问题.本文提出的FSLACK与EDD、LPT及SLACK进行了比较.随机订单的测试结果表明,本文提出的启发式规则在求解双目标带约束工件成类的平行机器调度问题上是有效的.这表明该算法可以应用在成型加工业的现场作业调度. 相似文献
9.
10.
并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。 相似文献
11.
本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法. 相似文献
12.
关于机器随机故障完工时间方差最小化单机调度问题 总被引:2,自引:0,他引:2
讨论了机器随机故障时,工件完工时间方差的期望最小化单机调度问题,其中描述机器故障的计数过程为广义泊松过程.推导出了目标函数等价的确定形式,而后进一步给出了工件加工时间相同时问题的最优解. 相似文献
13.
14.
15.
We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed. 相似文献
16.
《Applied Mathematical Modelling》2014,38(21-22):5231-5238
In this study we consider unrelated parallel machines scheduling problems with learning effect and deteriorating jobs, in which the actual processing time of a job is a function of joint time-dependent deterioration and position-dependent learning. The objective is to determine the jobs assigned to corresponding each machine and the corresponding optimal schedule to minimize a cost function containing total completion (waiting) time, total absolute differences in completion (waiting) times and total machine load. If the number of machines is a given constant, we show that the problems can be solved in polynomial time under the time-dependent deterioration and position-dependent learning model. 相似文献
17.
Batch processing happens in many different industries, in which a number of jobs are processed simultaneously as a batch. In this paper we develop two heuristics for the problem of scheduling jobs with release dates on parallel batch processing machines to minimize the makespan and analyze their worst-case performance ratios. We also present a polynomial-time optimal algorithm for a special case of the problem where the jobs have equal processing times. 相似文献
18.
讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况. 相似文献
19.
《European Journal of Operational Research》2006,175(2):769-781
The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n2) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times. 相似文献