在成组技术下带恶化和学习效应的单机排序问题

本文研究了带依靠时间的恶化效应和依靠位置的学习效应的成组排序问题。模型中,组安装时间是开始安装时间的线性函数,工件的加工时间带恶化和学习效应,目标函数分别为最小化时间表长问题和最小化总完工时间问题。基于对问题的分析,给出了多项式算法。     

同时具有学习效应和退化效应的单机排序问题

本文给出了一种同时具有一般化学习效应和退化效应的单机排序模型。在此模型中,工件的实际加工时间既与工件所在位置又与其开工时间有关,且工件在加工之后具有一个配送时间。其中学习效应是工件所在位置的函数,退化效应是工件开工时间的函数。证明了极小化最大完工时间和极小化总完工时间问题是多项式可解的,在满足一定的条件下,极小化加权总完工时间和极小化最大延误问题也是多项式可解的。推广了一些已有文献中的结论。     

具有一般学习效应的单机排序问题

在具有学习效应的环境下,由于机器重复加工相同或相似的工件,因此以后加工的工件的加工时间变小.本文研究新的更一般的学习效应:Dejong学习效应.我们证明单机最大完工时间问题,总完工时间问题和两类多目标问题是多项式时间可解的.     

具有时间与位置相关及维修限制的单机排序问题

考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则.     

具有凸资源约束的单机指数学习效应问题

研究在所有工件的正常加工时间均相同的情况下具有指数学习效应和凸资源约束的单机排序问题.给出了两种模型:在资源消耗总费用有限的情况下,以工件的最大完工时间为目标函数;在工件的最大完工时间有限的情况下,以资源消耗总费用为目标函数.求两种模型下的最优排序和最优资源分配,使得目标函数最小.证明这两个问题都是多项式时间可解的,并给出了相应的算法.     

一类具有学习效应和安装时间的单机排序问题

本文主要讨论了工件加工时间具有学习效应和安装时间的单机排序问题。工件的加工时间不仅与之前已加工完的工件加工时间有关,还与工件的加工位置有关。安装时间是依赖于已加工完的工件的实际加工时间的简单函数,即p-s-d形式。本文证明了极小化最大完工时间,极小化总完工时间,极小化完工时间的平方和问题具有多项式算法,也证明了极小化加权总完工时间,极小化最大延误和极小化总误工问题在某些条件下具有多项式算法。     

具有安装时间和学习效应的单机排序问题

讨论了工件具有安装时间和学习效应的单机排序问题。安装时间是依赖于已加工完的工件的实际加工时间的简单函数,即p-s-d形式。工件的加工时间不仅与已完成工件的加工时间有关,还与工件的加工位置有关。证明了极小化最大完工时间,极小化完工时间k总和,极小化完工时间k次幂的和是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误和极小化延迟时间和问题是多项式可解的。     

带有退化效应和序列相关运输时间的排序问题

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.     

具有学习和退化效应的单机干扰管理问题

针对工件同时具有学习和退化效应、机器具有可用性限制这一问题,建立可预见性单机干扰管理模型。在这一模型中,工件的加工时间是既与工件所排的加工位置又与工件开始加工的时间有关的函数。同时,在生产过程中由于机器发生故障或定期维修等扰动事件导致机器在某段时间内不能加工工件。目标是在同时考虑原目标函数和由扰动造成的偏离函数的情况下,构建一个新的最优时间表序列。根据干扰度量函数的不同研究了两个问题,第一个问题的目标函数是极小化总完工时间与总误工时间的加权和;第二个问题的目标函数是极小化总完工时间与总提前时间的加权和。对于所研究的问题,首先证明了最优排序具有的性质,然后建立了相应的拟多项式时间动态规划算法。     

原始工件的完工时间限制下的最小化最大延误时间的重新排序

考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.     

Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect

In this study, we introduce a time-dependent learning effect into a single-machine scheduling problem. The time-dependent learning effect of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. We introduce it into a single-machine scheduling problem and we show that it remains polynomially solvable for the objective, i.e., minimizing the total completion time on a single machine. Moreover, we show that the SPT-sequence is the optimal sequence in this problem.     

Scheduling deteriorating jobs with a learning effect on unrelated parallel machines

In this study we consider unrelated parallel machines scheduling problems with learning effect and deteriorating jobs, in which the actual processing time of a job is a function of joint time-dependent deterioration and position-dependent learning. The objective is to determine the jobs assigned to corresponding each machine and the corresponding optimal schedule to minimize a cost function containing total completion (waiting) time, total absolute differences in completion (waiting) times and total machine load. If the number of machines is a given constant, we show that the problems can be solved in polynomial time under the time-dependent deterioration and position-dependent learning model.     

Single machine scheduling with a time-dependent learning effect and deteriorating jobs

The paper deals with the single machine scheduling problems with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the processing time of a job is defined by function of its starting time and total normal processing time of jobs in front of it in the sequence. It is shown that even with the introduction of a time-dependent learning effect and deteriorating jobs to job processing times, the single machine makespan minimization problem remain polynomially solvable. But for the total completion time minimization problem, the classical shortest processing time first rule or largest processing time first rule cannot give an optimal solution.     

Minimizing the total completion time in a single-machine scheduling problem with a learning effect

This paper introduces a new time-dependent learning effect model into a single-machine scheduling problem. The time-dependent learning effect means that the processing time of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. In most related studies, the actual job processing time is assumed to be a function of its scheduled position when the learning effect is considered in the scheduling problem. In this paper, the actual processing time of a job is assumed to be proportionate to the length and position of the already scheduled jobs. It shows that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. It also shows that the shortest processing time (SPT) rule provides the optimum sequence for the addressed problem.     

A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect

This paper considers a scheduling model involving two agents, job release times, and the sum-of-processing-times-based learning effect. The sum-of-processing-times-based learning effect means that the actual processing time of a job of either agent is a decreasing function of the sum of the processing times of the jobs already scheduled in a given schedule. The goal is to seek for an optimal schedule that minimizes the total weighted completion time of the first agent, subject to no tardy job for the second agent. We first provide a branch-and-bound method to solve the problem. We then develop an approach that combines genetic algorithm and simulated annealing to seek for approximate solutions for the problem. We carry on extensive computational tests to assess the performance of the proposed algorithms.     

Note on “A note on single-machine group scheduling problems with position-based learning effect”

In a recent paper, Lee and Wu [W.-C. Lee, C.-C. Wu, A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model. 33 (2009) 2159–2163] proposed a new group scheduling learning model where the learning effect not only depends on the job position, but also depends on the group position. They investigate the makespan and the total completion time minimization problems on a single-machine. As for the total completion time minimization problem, they assumed that the numbers of jobs in each group are the same and the group normal setup and the job normal processing times are agreeable. Under the assumption conditions, they showed that the total completion time minimization problem can be optimally solved in polynomial time solution. However, the assumption conditions for the total completion time minimization problem do not reflect actual practice in many manufacturing processes. Hence, in this note, we propose other agreeable conditions and show that the total completion time minimization problem remains polynomially solvable under the agreeable conditions.     

Worst-case analysis for flow shop scheduling problems with an exponential learning effect

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with an exponential learning effect. By the exponential learning effect, we mean that the processing time of a job is defined by an exponent function of its position in a processing permutation. The objective is to minimize one of the four regular performance criteria, namely, the total completion time, the total weighted completion time, the discounted total weighted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single-machine scheduling problems. We also analyse the worst-case bound of our heuristic algorithms.     

Some single-machine scheduling problems with actual time and position dependent learning effects

In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively.     

Single-machine and two-machine flowshop scheduling with general learning functions

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.     

Single-machine ready times scheduling with group technology and proportional linear deterioration

Scheduling research has increasingly taken the concept of deterioration into consideration. In this paper, we study a single machine group scheduling problem with deterioration effect, where the jobs are already put into groups, before any optimization. We assume that the actual processing times of jobs are increasing functions of their starting times, i.e., the job processing times are described by a function which is proportional to a linear function of time. The setup times of groups are assumed to be fixed and known. For some special cases of minimizing the makespan with ready times of the jobs, we show that the problem can be solved in polynomial time for the proposed model. For the general case, a heuristic algorithm is proposed, and the computational experiments show that the performance of the heuristic is fairly accurately in obtaining near-optimal solutions. The results imply that the average percentage error of the proposed heuristic algorithm from optimal solutions is less than 3%.