共查询到19条相似文献,搜索用时 156 毫秒
1.
研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法. 相似文献
2.
含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性 总被引:2,自引:0,他引:2
本文研究含有批处理机的三台机器流水作业加工总长问题在某些情形下的计算复杂性。在批处理机上同时加工的工件组成一个工件批,一个工件批的所有工件同时开始、同时结束。当批处理机的容量有限时,我们证明了下列情形为强NP困难的:第一台机器是批处理机、其余两台机器是单机;第二台机器是单机、其余两台机器是批处理机;第三台机器是批处理机、其余两台机器是单机。 相似文献
3.
4.
考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。 相似文献
5.
研究目标函数为使最大完工时间达到最小的三台机器情况下的流水作业排序问题,同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内,存在称为运输时间的时间间隔,所有的运输工作均由自动机来完成,自动机在同一时间内最多运输一个工件,文章研究该问题及其特殊情况下的复杂性. 相似文献
6.
研究目标函数为使最大完工时间达到最小的三台机器情况下的流水作业排序问题, 同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内, 存在称为运输时间的时间间隔, 所有的运输工作均由自动机来完成, 自动机在同一时间内最多运输一个工件, 文章研究该问题及其特殊情况下的复杂性. 相似文献
7.
8.
研究了MapReduce系统中极小化最大完工时间的同类机排序问题.每个工件包含两类任务集:Map任务集和Reduce任务集.工件的Reduce任务必须在该工件的所有Map任务完成后才能开始加工.Map任务是可分的,即可以被任意分割并在多台机器上同时加工,而Reduce任务是不可分的.针对m台同类机离线模型,分别考虑了Reduce任务可中断和不可中断两种情形.对于可中断情形,设计了一个近似比为2-■的近似算法,其中g_1≥1,s_i为机器σ_i的加工速度且s_1≥s_2≥…≥s_m;对于不可中断情形,则给出了一个近似比为2+3~(1/2)/3的近似算法.上述结果是对已有文献的改进. 相似文献
9.
10.
11.
We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems. 相似文献
12.
We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only
compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. All jobs
are available at the same date. The capacity of the batch processing machine is finite or infinite. The processing time of
a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem
and present polynomial algorithms for several special cases. 相似文献
13.
This paper considers a two-machine multi-family scheduling problem with reentrant production flows. The problem consists of two machines, M1 and M2, and each job has the processing route (M1, M2, M1, M2). There are identical jobs in the same family and the jobs in the same family are processed in succession. Each machine needs a setup time before the first job in a family is processed. The objective is to minimize the maximum completion time. Examples of such a problem occur in the bridge construction, semiconductor industry and job processing on numerical controlled machines, where they usually require that the jobs are reprocessed once and there are identical jobs in the same family. This problem is shown to be NP-hard. A branch-and-bound algorithm is proposed, and computational experiments are provided. 相似文献
14.
《European Journal of Operational Research》2005,162(1):112-121
A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques. 相似文献
15.
Family sequencing and cooperation 总被引:1,自引:0,他引:1
Soesja Grundel Barış Çiftçi Peter Borm Herbert Hamers 《European Journal of Operational Research》2013
This paper analyzes a single-machine scheduling problem with family setup times both from an optimization and a cost allocation perspective. In a family sequencing situation jobs are processed on a single machine, there is an initial processing order on the jobs, and every job within a family has an identical cost function that depends linearly on its completion time. Moreover, a job does not require a setup when preceded by another job from the same family while a family specific setup time is required when a job follows a member of some other family. 相似文献
16.
本文考虑下述由多工类工件组成的订单的单机排序问题:每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类.当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si.每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间.我们希望适当排列这n个工件,使得订单的迟后范围最小.相应这一排序问题,文中依不同的背景给出了以下二种模式:同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示;同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示.对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法. 相似文献
17.
The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates 总被引:1,自引:0,他引:1
Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line
environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing
Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine
problem without release dates. According to WSPR, whenever a machine completes a job, the next job assigned to it is the one
with the least ratio of processing requirement to weight among all jobs available for processing at this point in time. We
analyze the performance of this heuristic and prove that its asymptotic competitive ratio is one for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a
solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic
assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation
of the problem.
Research supported in part by ONR Contracts N00014-90-J-1649 and N00014-95-1-0232, NSF Contracts DDM-9322828, DMI-9732795,
DMI-0085683 and DMI-0245352, NUS Academic Research Grant R314-000-046-112, and a research grant from the Natural Sciences
and Research Council of Canada (NSERC). 相似文献
18.
《European Journal of Operational Research》2001,135(1):177-183
Jobs are processed by a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource, which may be different from that for the jobs. Polynomial time algorithms are presented to find an optimal batch sequence and resource values such that either the total weighted resource consumption is minimized, subject to meeting job deadlines, or the maximum job lateness is minimized, subject to an upper bound on the total weighted resource consumption. The algorithms are based on linear programming formulations of the corresponding problems. 相似文献
19.
《European Journal of Operational Research》2005,162(1):184-190
In this paper we consider the problem of minimizing number of tardy jobs on a single batch processing machine. The batch processing machine is capable of processing up to B jobs simultaneously as a batch. We are given a set of n jobs which can be partitioned into m incompatible families such that the processing times of all jobs belonging to the same family are equal and jobs of different families cannot be processed together. We show that this problem is NP-hard and present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also show that when the jobs of a family have a common due date the problem can be solved by a pseudo-polynomial time procedure. 相似文献