共查询到20条相似文献,搜索用时 171 毫秒
1.
考虑已知工件最大加工时间的两台同类机半在线问题.机器M1,M2的速度分别为s1=1,s2=s(s≥1),工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的,目标函数为极小化最大机器负载.此模型简记为Q2/known largest job/Cmax.作者给出了Qmax2算法并证明此算法的竞争比为2(s 1)/s 2(1≤s≤2)和(s 1)/s(s>2),且是紧的.同时给出Q2/known largest job/Cmax问题的一个下界,并且证明Qmax2算法的竞争比与最优算法竞争比之差不大于1/4. 相似文献
2.
两台平行机的实时到达在线排序 总被引:2,自引:0,他引:2
本文考虑一的的在线平行机排序模型--实时到达在线问题,该模型中,工件是陆续到达的,工件的个数及到达时间是事先未知的,而且只有当工件到达,才知其加工时间,所求目标是使所有工件都加工完的时间达到最小,对两台平行机的情形,Chen与Vestjens给出近似比为3/2的线LPT算法,并证明了不存在近似小于(5-√5)/2的算法,我们利用黄金分割数设计了一个 算法,其近似比不超过(18-√5)/11。 相似文献
3.
本文首先证明排序问题1/rj/Cmax的“随手加工”法则,然后在此基础上对1/rj,UET/Lmax∩Cmax给出一个多项式最优化算法. 相似文献
4.
5.
6.
考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法. 相似文献
7.
8.
9.
本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题.这个问题来源于半导体制造过程中对芯片煅烧工序的排序.煅烧炉可以看成一个能同时最多加工B(〈n)个工件的处理机.此外,每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间.该问题就是将工件分批后再依批次的排序加工,使得所有工件都交付后所需的时间最短.我们设计了一个用时O(f(l/ε)n^5/2)的多项式时间近似方案,其中关于1/ε的指数函数厂(1/ε)对固定的ε是个常数. 相似文献
10.
11.
Mohammad Mahdavi Mazdeh Farzad ZaerpourAbalfazl Zareei Ali Hajinezhad 《Applied Mathematical Modelling》2010
This paper studies the parallel machines bi-criteria scheduling problem (PMBSP) in a deteriorating system. Sequencing and scheduling problems (SSP) have seldom considered the two phenomena concurrently. This paper discusses the parallel machines scheduling problem with the effects of machine and job deterioration. By the machine deterioration effect, we mean that each machine deteriorates at a different rate. This deterioration is considered in terms of cost which depends on the production rate, the machine’s operating characteristics and the kind of work done by each machine. Moreover, job processing times are increasing functions of their starting times and follow a simple linear deterioration. The objective functions are minimizing total tardiness and machine deteriorating cost. The problem of total tardiness on identical parallel machines is NP-hard, thus the problem with machine deteriorating cost as an additional term is also NP-hard. We propose the LP-metric method to show the importance of our proposed multi-objective problem. A metaheuristic algorithm is developed to locate optimal or near optimal solutions based on a Tabu search mechanism. Numerical examples are presented to show the efficiency of this model. 相似文献
12.
《European Journal of Operational Research》1996,94(2):277-283
The single machine batch scheduling problem is studied. The jobs in a batch are delivered to the customer together upon the completion time of the last job in the batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and its completion time. The objective is to minimize the sum of the batch delivery and job earliness penalties. A relation between this problem and the parallel machine scheduling problem is identified. This enables the establishment of complexity results and algorithms for the former problem based on known results for the latter problem. 相似文献
13.
The single machine parallel batch problem with job compatibility is considered to minimize makespan,where the job compatibility constraints are represented by a graph G.This problem is proved to be NP-hard.And when the graph G is limited to be a general bipartite,a complete bipartite and a complete m-partite graph,these problems are solved in polynomial time respectively. 相似文献
14.
考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案. 相似文献
15.
Radosław Rudek 《Journal of Global Optimization》2017,68(4):799-814
In this paper, we analyse the parallel machine makespan minimization problem with the general sum of processing time based learning or aging effects. First, we prove that an optimal solution to the single machine case can be found by priority rules. Next, for the considered parallel machine problem, we construct the exact dynamic programming algorithm that can operate on real-valued job processing times, which is the only exact algorithm for the analysed problem. The computational analysis confirms that it can solve optimally moderate problem instances. 相似文献
16.
Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes. 相似文献
17.
We investigate the integrated production and distribution scheduling problem in a supply chain. The manufacturer’s production environment is modeled as a parallel machine system. A single capacitated vehicle is employed to deliver products in batches to multiple customers. The scheduling problem can also be viewed as either parallel machines with delivery considerations or a flexible flowshop. Different inventory holding costs, job sizes (volume or storage space required in the transportation unit), and job priorities are taken into account. Efficient mathematical modeling and near-optimal heuristic approaches are presented for minimizing total weighted completion time. 相似文献
18.
19.
Adam Janiak Tomasz Krysiak Costas P. Pappis Theodore G. Voutsinas 《European Journal of Operational Research》2009
This paper deals with a problem of scheduling jobs on the identical parallel machines, where job values are given as a power function of the job completion times. Minimization of the total loss of job values is considered as a criterion. We establish the computational complexity of the problem – strong NP-hardness of its general version and NP-hardness of its single machine case. Moreover, we solve some special cases of the problem in polynomial time. Finally, we construct and experimentally test branch and bound algorithm (along with some elimination properties improving its efficiency) and several heuristic algorithms for the general case of the problem. 相似文献
20.
研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法. 相似文献