共查询到18条相似文献,搜索用时 46 毫秒
1.
本文讨论FlowShop排序问题Fm|prmu|∑ωjCj给出了求解该问题的一个分枝定界法. 相似文献
2.
本文给出了Flow shop排序问题Fm/prmu/∑^WjCj的一个启发式算式,其最坏情况的界为m,且是紧界。 相似文献
3.
极小化加权完工时间和的Flowshop问题的算法 总被引:3,自引:0,他引:3
本文讨论了极小化加权完工时间和的Flowshop问题.我们给出了一个最坏情况误差界为m的启发式算法,对于m=2的情况,如果工件具有一致权因子,即pi相似文献
4.
5.
Baker和Nuttle提出了下述单可变资源排序问题:$n$个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan、Cheng 和 Ng 证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的. 相似文献
6.
Baker和Nuttle提出了下述单可变资源排序问题:扎个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan、Cheng和Ng证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的. 相似文献
7.
考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法. 相似文献
8.
各机器具有相同加工时间的Flow Shop 成组排序问题 总被引:2,自引:0,他引:2
本文讨论了m台机器的Folw Shop成组排序问题,工件在不同机器上的加工时间相同,目标函数为极小化完工时间和。给出了一个多项式时间可解的最优算法。 相似文献
9.
10.
11.
Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time 总被引:1,自引:0,他引:1
C. T. Ng T. C. Edwin Cheng Adam Janiak Mikhail Y. Kovalyov 《Annals of Operations Research》2005,133(1-4):163-174
The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence
independent setup time preceding the processing of each group. The setup times and the job processing times are controllable
through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource.
Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms
are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total
weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial
enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming.
This research was supported in part by The Hong Kong Polytechnic University under grant number G-T246 and the Research Grants
Council of Hong Kong under grant number PolyU 5191/01E. In addition, the research of M.Y. Kovalyov was supported by INTAS
under grant number 00-217. 相似文献
12.
Jatinder N. D. Gupta Volker Lauff Frank Werner 《Journal of Mathematical Modelling and Algorithms》2004,3(2):123-151
We consider a two-machine flow shop problem with a common due date where the objective is to minimize the sum of functions which penalize early as well as tardy completion of jobs. Since the problem is NP-hard in the strong sense, we investigate some general properties of optimal schedules for the problem, we develop lower and upper bounds, derive dominance criteria, and propose an enumerative algorithm for finding an optimal schedule. The performance of the proposed algorithm together with the influence of the individual components is thoroughly discussed. 相似文献
13.
14.
An Enhanced TSP-Based Heuristic for Makespan Minimization in a Flow Shop with Setup Times 总被引:1,自引:0,他引:1
This paper presents an enhanced heuristic for minimizing the makespan of the flow shop scheduling problem with sequence-dependent setup times. The procedure transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes for both large setup times and bad fitness of schedule. This hybrid cost function is an improvement over earlier approaches that penalized for setup times only, ignoring the flow shop aspect of the problem. To establish good parameter values, each component of the heuristic was evaluated computationally over a wide range of problem instances. In the testing stage, an experimental comparison with a greedy randomized adaptive search procedure revealed the conditions and data attributes where the proposed procedure works best. 相似文献
15.
混合作业是经典的自由作业和异序作业的一种综合,其中一些工件可以按任意的机器顺序进行处理,而另一些工件必须遵守预先指定的机器顺序.本文研究安装、加工和拆卸时间分离的两台机器混合作业排序问题,该问题已经被知道是强NP困难的,本文把流水作业中的同顺序作业概念推广到混合作业,并得到这个混合作业问题在同顺序意义下的最优解,这个解对于一般情形是3/2近似解,但对于一些有意义的特殊情形是整体最优的. 相似文献
16.
本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形,并给出了性能比为3/2的近似算法。同时我们还考虑了在第二台机器上存在一个不可用时间段情况下的半在线问题,给出了一个竞争比为3/2的半在线算法。 相似文献
17.
对二台机器流作业中的Lot-Strcaming问题(简称LS),以往的研究多为固定分批数寻找各批大小,或对二台机器引入相同的调整时间,寻找量优分批数及和批大小,本文对机器1,2每生产一个新的子批量分别引入一独立的调整时间S1,S2,研究同时决定最优分批数和最优分批大小,并给出相应的最优算法。 相似文献
18.
资源有限的加权总完工时间单机排序问题 总被引:1,自引:0,他引:1
本讨论资源有限的加权总工时间单机排序问题,对现在仍为OPEN问题1|pj=bj-ajuj,∑uj≤U|∑wjCj给出了一个有关最优解中最优资源分配的重要性质,并利用该性质分别给出了三种情况bj=b,wj=w,aj=a;bj=b,wj=w,uj=u;aj=a,wj=w,uj=u的最优算法。 相似文献