Scheduling jobs with a general learning effect model

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.     

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

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

Single-machine group scheduling with general deterioration and learning effects

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.     

Trapezoidal type inequalities for n-time differentiable functions

In this paper we consider the flow shop scheduling problems with the effects of learning and deterioration. In this model the processing times of a job is defined as a function of its starting time and position in a sequence. The scheduling objective functions are makespan and total completion time. We prove that even with the introduction of learning effect and deteriorating jobs to job processing times, some special flow shop scheduling problems remain polynomially solvable.     

基于一般学习效应下的单机排序问题

近来具有学习效应的机器排序问题收到广泛的关注.对于机器排序中工件的实际加工来说,与工件加工位置有关的学习模型更具有现实性.本文研究了工件加工位置和与已经加工过的工件之和有关的一般学习效应模型.首先证明文献中与位置和已经加工过的工件加工时间之和有关的学习模型是本模型的特殊情形.其次对于单机排序问题我们提出一般解法.     

Scheduling with a position-weighted learning effect

In general, human learning takes time to build up, which results from a worker gaining experience from repeating similar operations over time. In the early stage of processing a given set of similar jobs, a worker is not familiar with the operations, so his learning effect on the jobs scheduled early is not apparent. On the other hand, when the worker has gained experience in processing the jobs his learning improves. So a worker’s learning effect on a job depends not only on the total processing time of the jobs that he has processed but also on the job position. In this paper we introduce a position-weighted learning effect model for scheduling problems. We provide optimal solutions for the single-machine problems to minimize the makespan and the total completion time, and an optimal solution for the single-machine problem to minimize the total tardiness under an agreeable situation. We also consider two special cases of the flowshop problem.     

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

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

带恶化和综合学习效应的成组排序问题研究

本文研究了成组技术下带恶化和综合学习效应的排序问题,工件的加工时间带综合学习效应。对最小化时间表长问题,我们给出了多项式算法,并且证明了带一致关系的最小化总完工时间问题也是多项式可解的。     

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 scheduling with a general sum-of-actual-processing-times-based and job-position-based learning effect

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.     

A note on “Single-machine scheduling problems with both deteriorating jobs and learning effects”

The main results in a recent paper [1] (J.-B. Wang, D. Wang, G.-D. Zhang, Single-machine scheduling problems with both deteriorating jobs and learning effects, Appl. Math. Model. 34 (2010) 2831–2839) are incorrect because job processing times are variable due to both deteriorating jobs and learning effects, which is not taken into account by the authors. In this note, we show by counter-examples that some published results are incorrect.     

Several single-machine scheduling problems with general learning effects

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$\theta ?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.     

Single-machine scheduling problems with a learning effect

In many situations, the skills of workers continuously improve when repeating the same or similar tasks. This phenomenon is known as the “learning effect” in the literature. In most studies, the learning phenomenon is implemented by assuming the actual job processing time is a function of its scheduled position [D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res. 115 (1999) 173–178]. Recently, a new model is proposed where the actual job processing time depends on the sum of the processing times of jobs already processed [C. Koulamas, G.J. Kyparisis, Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res. 178 (2007) 402–407]. In this paper, we extend their models in which the actual job processing time not only depends on its scheduled position, but also depends on the sum of the processing times of jobs already processed. We then show that the single-machine makespan and the total completion time problems remain polynomially solvable under the proposed model. In addition, we show that the total weighted completion time has a polynomial optimal solution under certain agreeable solutions.     

Single-machine group scheduling problems with deteriorated and learning effect

In many realistic situation, a job processed later consumes more time than the same job when it is processed earlier, this phenomenon is known as deteriorated effect. The skills of workers continuously improve when repeating the same or similar tasks, this phenomenon is as the “learning effect” in the literature. However, most studies considering the deteriorated and learning effect ignore the fact that production efficiency can be increased by grouping various parts and products with similar designs and/or production processes. This phenomenon is known “group technology” in the literature. In this paper, we propose a new group scheduling with deteriorated and learning model where the learning effect not only depends on job position, but also depends on the group position; the deteriorated effect depends on its starting time of the job. We then show that the single-machine makespan and the total completion time problems remain polynomial optimal solvable under the proposed model. In addition, we show the maximum lateness have a polynomial optimal solution under certain agreeable restriction.     

Some single-machine scheduling problems with elapsed-time-based and position-based learning and forgetting effects

In this paper, a generalized model with past-sequence-dependent learning and forgetting effects is proposed. Both effects are assumed to be dependent on the sum of processing time as well as the scheduling position. Based on this model, we investigate and prove that some single-machine problems remain polynomially solvable with certain agreeable conditions. We further show that many models known in the literature are special cases of our proposed model. Several helpful lemmas are presented to analyze single-machine scheduling problems with various objective functions: makespan, total completion time, weighted completion time, and maximum lateness.     

Single-machine scheduling with a sum-of-actual-processing-time-based learning effect

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.     

Single-machine scheduling simultaneous with position-based and sum-of-processing-times-based learning considerations under group technology assumption

This paper considers the problems of scheduling with the effect of learning on a single-machine under group technology assumption. We propose a new learning model where the job actual processing time is linear combinations of the scheduled position of the job and the sum of the normal processing time of jobs already processed. We show that the makespan minimization problem is polynomially solvable. We also prove that the total completion time minimization problem with the group availability assumption remains polynomially solvable under agreeable conditions.     

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

In many situations, the skills of workers continuously improve when repeating the same or similar tasks. This phenomenon is known as the “learning effect” in the literature. However, most studies considering the learning effect ignore the fact that production efficiency can be increased by grouping various parts and products with similar designs and/or production processes. This phenomenon is known as “group technology” in the literature. In this paper, we propose a new group scheduling learning model where the learning effect not only depends on the job position, but also depends on the group position. We then show that the makespan and the total completion time problems remain polynomially solvable under the proposed model.     

Application of an optimization problem in Max-Plus algebra to scheduling problems

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed.     

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.