共查询到20条相似文献,搜索用时 15 毫秒
1.
考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法. 相似文献
2.
为了研究考虑公共交货期窗口问询的退化工件排序问题,构建了极小化因提前时间、延误时间以及交货期窗口问询产生的总成本的单机排序调度决策模型。模型假定所有工件的交货期窗口一致,且窗口的开始时间、窗口大小为决策变量;工件具有差异化的退化因子;工件的实际加工时间与其开始加工时间、退化因子呈线性关系。分析了交货期窗口决策和工件排序具有的最优性质,以及最优的工件排序与工件退化因子之间的关系,并提出了最优算法。研究表明:可基于工件的退化因子确定最优工件加工顺序,最优交货期窗口的开始时间和结束时间分别对应于最优序中某个工件的完工时间,研究问题可在多项式时间内进行求解。 相似文献
3.
Stanis?aw Gawiejnowicz Wies?aw Kurc Lidia Pankowska 《Discrete Applied Mathematics》2006,154(15):2150-2166
In the paper a single machine time-dependent scheduling problem is considered. The processing time pj of each job is described by a function of the starting time t of the job, pj=1+αjt, where the job deterioration rate αj?0 for j=0,1,…,n and t?0. Jobs are nonpreemptable and independent, there are no ready times and no deadlines. The criterion of optimality of a schedule is the total completion time.First, the notion of a signature for a given sequence of job deterioration rates is introduced, two types of the signature are defined and their properties are shown. Next, on the basis of these properties a greedy polynomial-time approximation algorithm for the problem is formulated. This algorithm, starting from an initial sequence, iteratively constructs a new sequence concatenating the previous sequence with new elements, according to the sign of one of the signatures of this sequence.Finally, these results are applied to the problem with job deterioration rates which are consecutive natural numbers, αj=j for j=0,1,…,n. Arguments supporting the conjecture that in this case the greedy algorithm is optimal are presented. 相似文献
4.
We investigate the computational complexity of deterministic sequencing problems in which unit-time jobs have to be scheduled on a single machine subject to chain-like precedence constraints. NP-hardness is established for the cases in which the number of late jobs or the total weighted tardiness is to be minimized, and for several related problems involving the total weighted completion time criterion. 相似文献
5.
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. 相似文献
6.
针对工件动态到达的在线调度模型提出了一种基于实例转换的竞争分析方法,该方法从问题的一个任意实例出发,逐步沿着性能比增加的方向修改工件的各种参数而得到结构更加简单特殊的实例,最后所导出的简单实例的性能比可以直接计算,且是算法竞争比的一个上界.该方法为在线调度算法的竞争比分析提供了一种新颖的、规律性的思路,以最小化总加权完工时间的单机在线调度问题为例,使用提出的分析方法为该问题一个已有的竞争分析结论提供了更加简洁明了的替代性证明. 相似文献
7.
关于机器随机故障完工时间方差最小化单机调度问题 总被引:2,自引:0,他引:2
讨论了机器随机故障时,工件完工时间方差的期望最小化单机调度问题,其中描述机器故障的计数过程为广义泊松过程.推导出了目标函数等价的确定形式,而后进一步给出了工件加工时间相同时问题的最优解. 相似文献
8.
9.
加工时间恶化的两个成组加工排序问题 总被引:1,自引:0,他引:1
ChengMingbao SunShijie 《高校应用数学学报(英文版)》2005,20(2):225-234
This paper considers single-machine scheduling problems in group technology with the jobs‘ processing times being simple linear functions of their start times. The objective functions are the minimizing of makespan and total weighted completion time. Some optimal conditions and algorithms are given and the fact that the problem of total weighted completion times is NP-hard is proved. 相似文献
10.
The single machine group scheduling problem is considered. Jobs are classified into several groups on the basis of group technology, i.e. jobs of the same group have to be processed jointly. A machine set-up time independent of the group sequence is needed between each two consecutive groups. A schedule specifies the sequence of groups and the sequence of jobs in each group. The quality of a schedule is measured by the criteriaF
1, ...,F
m ordered by their relative importance. The objective is to minimize the least important criterionF
m subject to the schedule being optimal with respect to the more important criterionF
m–1 which is minimized on the set of schedules minimizing criterionF
m–2 and so on. The most important criterion isF
1, which is minimized on the set of all feasible schedules. An approach to solve this multicriterion problem in polynomial time is presented if functionsF
1, ...,F
m have special properties. The total weighted completion time and the total weighted exponential time are the examples of functionsF
1, ...,F
m–1 and the maximum cost is an example of functionF
m for which our approach can be applied.The research of the authors was partially supported by a KBN Grant No. 3 P 406 003 05, the Fundamental Research Fund of Belarus, Project N 60-242, and the Deutsche Forschungsgemeinschaft, Project Schema, respectively. The paper was completed while the first author was visiting the University of Melbourne. 相似文献
11.
工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序. 相似文献
12.
研究了具有线性恶化工件的单机排序问题,其中线性恶化工件指的是工件的加工时间是开工时间的线性增长函数.在一般情况下,对目标函数为极小化完工时间平方和与极小化总误工数问题分别给出了最优算法.此外,在分段情况下,对目标函数为极小化最大完工时间问题也给出了最优算法. 相似文献
13.
14.
考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b2m2m2222m). 相似文献
15.
16.
考虑了当每分一批均产生固定费用、批容量有界且为固定值b、加工不允许中断抢先.所有工件在零时刻到达时的单机平行分批排序问题.目标是最小化总完工时间与分批费用之和.利用动态规划方法给出了多项式时间算法,时间界为O(n~(b(b-1))). 相似文献
17.
各机器具有相同加工时间的Flow Shop 成组排序问题 总被引:2,自引:0,他引:2
本文讨论了m台机器的Folw Shop成组排序问题,工件在不同机器上的加工时间相同,目标函数为极小化完工时间和。给出了一个多项式时间可解的最优算法。 相似文献
18.
研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法. 相似文献
19.
针对工件同时具有学习和退化效应、机器具有可用性限制这一问题,建立可预见性单机干扰管理模型。在这一模型中,工件的加工时间是既与工件所排的加工位置又与工件开始加工的时间有关的函数。同时,在生产过程中由于机器发生故障或定期维修等扰动事件导致机器在某段时间内不能加工工件。目标是在同时考虑原目标函数和由扰动造成的偏离函数的情况下,构建一个新的最优时间表序列。根据干扰度量函数的不同研究了两个问题,第一个问题的目标函数是极小化总完工时间与总误工时间的加权和;第二个问题的目标函数是极小化总完工时间与总提前时间的加权和。对于所研究的问题,首先证明了最优排序具有的性质,然后建立了相应的拟多项式时间动态规划算法。 相似文献
20.
The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem,n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weight. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each job in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem isNP-hard even if all due dates are equal. For the general case, we present a dynamic programming algorithm which solves the problem with equal weights inO(n
3) time. We formulate a certain scaled problem and show that our dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement ofO(n
3/ +n
3 logn). A side result is anO(n logn) algorithm for the problem of minimizing the maximum weight of late jobs.Supported by INTAS Project 93-257. 相似文献