共查询到19条相似文献，搜索用时 642 毫秒
1.
本考虑下述带磨损因子的排序问题：n个工件j，j=1，2，…，n，在同一台机器上依次加工，其所需的加工时间同它被开始加工的时间有关，越后加工其所需的加工时间越多；要求适当排列这n个工件的加工顺序，使目标函数值达最小．对加工全程、完工时间之和这两个目标函数中给出了相应条件下的最优算法． 相似文献
2.
研究一类带批安装时间的平行机排序问题。工件按时间到达,在任何时刻,只知道当前已经就绪工件的信息。工件成批加工,同一批中工件的完工时间为批中最后一个工件的完工时间,每批开工前有一个固定的批安装时间。目标函数为极小化所有工件的总完工时间。主要考虑两个到达时间且工件加工时间都相等的特殊情形,给出竞争比为3/2的在线算法,并且有实例说明此界为紧致的。 相似文献
3.
《佳木斯教育学院学报》2017,(2)
在经典排序模型中,我们往往假定机器必须加工所有的工件,并且它们的加工时间都是给定的。但是在许多现实的应用中,若某个工件的加工时间或者加工费用很大,我们就会考虑是否要加工该工件,我们既可以选择付出一定的费用而拒绝加工该工件也可以选择不付费而加工它。这时目标函数不再是传统的最大总完工时间,极小化最大完工时间,最大延迟等,而是要同时考虑费用,我们把这种排序称为可拒绝排序[1][2]。本文研究了工件带拒绝费用的单机分族分批排序问题。主要证明了问题1,sfg|family-jobs,rej|Cmax+∑j∈sej和1,sfg|family-jobs,rej,b|Cmax+jisej是NP-难的,给出了它们的近似算法。 相似文献
4.
石国春 《商丘师范学院学报》2010,26(12)
讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序. 相似文献
5.
6.
考虑了在工件具有学习效应的条件下,目标函数为最大完工时间和总完工时间的单机成组排序问题.对这两个问题分别给出了多项式时问算法并证明了其算法的最优性. 相似文献
7.
韩翔凌 《廊坊师范学院学报(自然科学版)》2010,10(6)
讨论了分批排序中工件具有学习效应、目标函数为极小化加权总完工时间的几个问题,分别就所有工件的基本加工时间都相等的情况给出了几种算法,并证明了算法的最优性. 相似文献
8.
研究了工件有优先约束和尺寸大小关系的分批排序问题,这里目标函数为工件的极大完工时间,这类问题是NP—完备的.对工件加工时间相同和有特殊到达时间的情况给出了它的近似算法,并证明其最差性能比不超过2. 相似文献
9.
曹国梅 《常熟理工学院学报》2009,23(4):22-24
考虑极小化加权总完工时间的一类无界的不相容工件族分批排序问题,给出了最优排序的性质和算法,并加以证明．对工件有k个到达时间的情形,给出了一个复杂性为D（2^k-1nlogn）的启发式算法． 相似文献
10.
黄宜坤 《临沂师范学院学报》2006,28(6):20-23
主要研究关于工件加工时间恶化的若干问题,给出了最大完工时间问题的一些性质、总完工时间问题的算法和性质,并根据实际问题,设计了一些新模型,相应地给出了该问题所具有的性质及一些简单算法． 相似文献
11.
严培胜 《黄冈师范学院学报》2004,24(6):21-25,36
对于单机的排序与工期分配问题．于刚曾经给出了一些结果．本文则考虑成组加工时总误工问题的排序与工期分配．对于不同模式．或给出其最优序．或转化为目前研究得比较成熟的问题． 相似文献
12.
关于简单线性恶化问题的平行机排序的一个全多项式逼近算法 总被引：1，自引：0，他引：1
In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines. 相似文献
13.
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p＞1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine's load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented. 相似文献
14.
为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的. 相似文献
15.
A single machine scheduling problem involving fuzzy due dates and fuzzy precedence constraints is investigated. The fuzzy precedence reflects the satisfaction level with respect to precedence between two jobs. A membership function is associated with each job Ji, which describes the degree of satisfaction with respect to completion time of Ji. For the bi-criteria scheduling problem, an 0 （ n^3 ） algorithm is proposed for finding nondominated solutions. 相似文献
16.
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications.
For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task
arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine
scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems
are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further
information about the tasks is available, which allows the improvement of the performance of the best possible algorithms.
Problems of this class are called semi-online ones. In this paper, the semi-online problemP2|decr|l
p (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum
of thel
p norm of every machine's load. It is shown thatLS algorithm is optimal for anyl
p norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problemsP2|online|l
p andP2|decr|l
p are presented.
Project supported by the National Natural Science Foundation of China (Nos. 10271110, 10301028) and the Teaching and Research
Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China 相似文献
17.
本文研究两台平行同类机的一个半在线排序问题。当机器是有准备时间的同类机时,总加工时间已知,文章给出了一个竞争比至少为的半在线算法,同时给出了证明。 相似文献
18.
研究预防性周期维护策略下再制造系统中可中断和不可中断2类工件的单机调度问题.以最小化完工时间为目标,提出了LPT-LS算法,该算法首先按LPT(longest processing time)规则安排不可中断工件,然后按LS(list scheduling)规则安排可中断工件.并根据可中断工件的总加工时间(记为S2)分3种情况证明了该算法的最坏情况比,结论如下:当S2大于按LPT规则安排不可中断工件后机器的空闲时间时,最坏情况比为1;当S2介于分别按LPT规则和OPT(最优排序)规则安排不可中断工件后机器的空闲时间之间时,最坏情况比小于2;当S2小于按OPT规则安排不可中断工件后机器的空闲时间时,最坏情况比小于2.最后通过算例验证了结论的正确性. 相似文献
19.
讨论了带有学习效应的排序问题,目标函数为超前有奖延误受罚的几个问题.对所有工件加工时间不相同和相同的情形,分别给出了算法,并证明了算法的最优性. 相似文献