共查询到19条相似文献,搜索用时 218 毫秒
1.
2.
本文主要讨论了工件加工时间具有学习效应和安装时间的单机排序问题。工件的加工时间不仅与之前已加工完的工件加工时间有关,还与工件的加工位置有关。安装时间是依赖于已加工完的工件的实际加工时间的简单函数,即p-s-d形式。本文证明了极小化最大完工时间,极小化总完工时间,极小化完工时间的平方和问题具有多项式算法,也证明了极小化加权总完工时间,极小化最大延误和极小化总误工问题在某些条件下具有多项式算法。 相似文献
3.
4.
重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达,新工件的安排使得原始工件重新排序而产生错位.考虑了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题.工件的位置错位和时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化最大延迟问题.其中退化效应是指其实际加工时间是开工时间的非减函数,工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差,工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差.对以上两类问题,当权重系数或者错位限制满足特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列,基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法. 相似文献
5.
针对工件同时具有学习和退化效应、机器具有可用性限制这一问题,建立可预见性单机干扰管理模型。在这一模型中,工件的加工时间是既与工件所排的加工位置又与工件开始加工的时间有关的函数。同时,在生产过程中由于机器发生故障或定期维修等扰动事件导致机器在某段时间内不能加工工件。目标是在同时考虑原目标函数和由扰动造成的偏离函数的情况下,构建一个新的最优时间表序列。根据干扰度量函数的不同研究了两个问题,第一个问题的目标函数是极小化总完工时间与总误工时间的加权和;第二个问题的目标函数是极小化总完工时间与总提前时间的加权和。对于所研究的问题,首先证明了最优排序具有的性质,然后建立了相应的拟多项式时间动态规划算法。 相似文献
6.
考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则. 相似文献
7.
本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了p_(ij)=p_i(i=1,…,m;j=1,…,n)这种情况,当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法. 相似文献
8.
讨论了工件具有安装时间和学习效应的单机排序问题。安装时间是依赖于已加工完的工件的实际加工时间的简单函数,即p-s-d形式。工件的加工时间不仅与已完成工件的加工时间有关,还与工件的加工位置有关。证明了极小化最大完工时间,极小化完工时间k总和,极小化完工时间k次幂的和是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误和极小化延迟时间和问题是多项式可解的。 相似文献
9.
本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个工件的完工时间已确定每个工件的承诺交付时间。然而,在工件正式开始加工前,原计划用于加工的某段时间区间因临时用于检修机器而导致机器在该时间区间不再可用,需要对工件重新排序。为了确保在新的重新排序中,工件的延误成本不致太大,决策者可以选择拒绝部分工件,但需支付相应的拒绝费用。任务是确定接受工件集和拒绝工件集,并将接受的工件在考虑机器具有不可用区间的条件下重新排序使得接受工件集的总加权完工时间,总拒绝费用及赋权最大延误之和最小。该问题是NP-困难的,对此给出了伪多项式时间动态规划精确算法,利用稀疏技术设计了完全多项式时间近似方案。 相似文献
10.
研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS). 相似文献
11.
In this paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. 相似文献
12.
In this paper, we consider the single machine scheduling problems with an actual time-dependent deterioration effect. By the actual time-dependent deterioration effect, we mean that the processing time of a job is defined by increasing function of total actual processing time of jobs in front of it in the sequence. We show that even with the introduction of an actual time-dependent deterioration to job processing times, makespan minimization problem, total completion time minimization problem, the total lateness, and the sum of the quadratic job completion times minimization problem remain polynomially solvable, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, and the total tardiness minimization problem can be solved in polynomial time under certain conditions. 相似文献
13.
The paper deals with single machine scheduling problems with setup time considerations where the actual processing time of a job is not only a non-decreasing function of the total normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We consider the following objective functions: the makespan, the total completion time, the sum of the δth (δ ≥ 0) power of job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the δ th (δ ≥ 0) power of job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. 相似文献
14.
In this paper we consider the single machine past-sequence-dependent (p-s-d) setup times scheduling problems with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects, we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem, maximum tardiness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions. 相似文献
15.
In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. 相似文献
16.
We consider several single machine scheduling problems in which the processing time of a job is a linear function of its starting time and jobs can be rejected by paying penalties. The objectives are to minimize the makespan, the total weighted completion time and the maximum lateness/tardiness plus the total penalty of the rejected jobs. We show that these problems are NP-hard, and design algorithms based on dynamic programming (including pseudo-polynomial time optimal algorithms and fully polynomial time approximation schemes) to solve them. 相似文献
17.
In this paper, we bring into the scheduling field a general learning effect model where the actual processing time of a job is not only a general function of the total actual processing times of the jobs already processed, but also a general function of the job’s scheduled position. We show that the makespan minimization problem and the sum of the kth power of completion times minimization problem can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. 相似文献
18.
J-B Wang 《The Journal of the Operational Research Society》2010,61(1):172-177
In this paper we consider the single-machine scheduling problems with a sum-of-actual-processing-time-based learning effect. By the sum-of-actual-processing-time-based learning effect, we mean that the processing time of a job is defined by a function of the sum of the actual processing time of the already processed jobs. We show that even with the introduction of the sum-of-actual-processing-time-based learning effect to job processing times, the makespan minimization problem, the total completion time minimization problem, the total completion time square minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem remain polynomially solvable, respectively. 相似文献
19.
In this paper we consider several single-machine scheduling problems with general learning effects. By general learning effects, we mean that the processing time of a job depends not only on its scheduled position, but also on the total normal processing time of the jobs already processed. We show that the scheduling problems of minimization of the makespan, the total completion time and the sum of the θ th (θ?0) power of job completion times can be solved in polynomial time under the proposed models. We also prove that some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time. 相似文献