共查询到18条相似文献,搜索用时 78 毫秒
1.
2.
3.
研究具有加工时间之和学习效应下的一个新型成组排序问题,工件的学习效应是之前工件加工时间之和的函数,组学习效应是成组加工所在的位置的函数. 考虑最大完工时间和总完工时间两个问题,证明了这两个问题都是多项式时间可解的,并提出了相应的多项式时间算法. 相似文献
4.
在工业生产中,随着员工操作技能的熟练程度的增加,对于相同的任务越往后加工,所花的时间将会减少。 同时,为了尽早完工,管理者也会考虑给加工工件分配一定量的额外资源来缩短工件加工时间。 本文基于以上实例,讨论了工件的实际加工时间既具有学习效应又依赖所分配资源的单机排序问题。 在问题中,假设工件的学习效应是之前已加工工件正常加工时间和的指数函数。 同时随着分配给工件资源量的增加,工件的实际加工时间呈线性减少,所需费用呈线性增加。对这一排序模型,主要探讨以下五个目标函数:最小化最大完工时间与资源消耗量总费用的和;最小化总完工时间与资源消耗量总费用的和;最小化加权总完工时间与资源消耗量总费用的和;最小化总提前、总延误、总共同交货期与资源消耗量总费用的和以及最小化总提前、总延误、总松弛交货期与资源消耗量总费用的和。 本文对前三个目标函数相应的排序问题给出了多项式时间可求解的算法。 对后两个目标函数所涉及的排序问题借助于指派问题分别给出了时间复杂性为O(n3)的算法。 相似文献
5.
6.
重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达,新工件的安排使得原始工件重新排序而产生错位.考虑了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题.工件的位置错位和时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化最大延迟问题.其中退化效应是指其实际加工时间是开工时间的非减函数,工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差,工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差.对以上两类问题,当权重系数或者错位限制满足特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列,基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法. 相似文献
7.
8.
考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决. 相似文献
9.
10.
11.
In this paper we consider single-machine group scheduling problems with effects of learning and deterioration at the same time. By effects of learning and deterioration, we mean that the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent and time-dependent learning effects. The objective of scheduling problems is to minimize the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model. 相似文献
12.
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. 相似文献
13.
In this paper, we show that the main results in a recent paper by Zhang and Yan [X. Zhang and G. Yan, Machine scheduling problems with a general learning effect, Mathematical and Computer Modelling 51 (2010) 84–90] are incorrect as an important reason is missing, that is, the processing time of a job is variable according to a general learning effect. Here we point out these wrong results by a counter-example. In addition, we give a revised model with a general learning effect. We show that some single machine scheduling problems are still polynomially solvable under the revised model. We also show that some special cases of the flowshop scheduling problems can be solved in polynomial time under the revised model. 相似文献
14.
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. 相似文献
15.
B M T Lin 《The Journal of the Operational Research Society》2007,58(8):1099-1102
This note presents complexity results for a single-machine scheduling problem of minimizing the number of late jobs. In the studied problem, the processing times of the jobs are defined by positional learning effects. A recent paper proposed a polynomial time algorithm for the case with a common due date and conjectured the general problem to be ????-hard. We confirm that the general problem is strongly ????-hard and show that the studied problem remains ????-hard even if there are only two different due-date values. 相似文献
16.
The paper deals with machine scheduling problems with a general learning effect. By the general learning effect, we mean that the actual processing time of a job is not only a non-increasing function of the total weighted normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence, where the weight is a position-dependent weight. We show that even with the introduction of a general learning effect to job processing times, some single machine scheduling problems are still polynomially solvable under the proposed model. We also show that some special cases of the flow shop scheduling problems can be solved in polynomial time. 相似文献
17.