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.     

Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs

We study a single-machine scheduling and due window assignment problem, in which job processing times are defined by functions of their starting times (deteriorating effect) and positions in the sequence (learning effect). The problem is to determine the optimal due windows and the processing sequence simultaneously to minimize costs for earliness, tardiness, the window location, window size and makespan. We show that the problem remains polynomially solvable under the proposed model for two popular due window assignment methods: The slack due date assignment method (usually referred to as SLK) and the unrestricted due date assignment method (usually referred to as DIF).     

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.     

Minimizing makespan in a two-machine flow shop with effects of deterioration and learning

We consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the makespan. Several dominance properties and two lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. Two heuristic algorithms are also proposed to obtain near-optimal solutions. Computational results are presented to evaluate the performance of the proposed algorithms.     

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.     

Common due date scheduling with autonomous and induced learning

Up to now the few existing models, that consider learning effects in scheduling, concentrate on learning-by-doing (autonomous learning). But recent contributions to the literature on learning in manufacturing organizations emphasize the important impact of proactive investments in technological knowledge on the learning rate (induced learning). In the present paper, we focus on a scheduling problem where the processing times decrease according to a learning rate, which can be influenced by an initial cost-inducing investment. Thus we have integrated into our model both aspects of learning––autonomous and induced––thereby highlighting the management's responsibility to invest in technological knowledge enhancement. We have been able to derive some structural properties of the problem and present a polynomially bound solution procedure which optimally solves the problem by using these properties. The optimal solution to the scheduling problem contains––of course–– information on the optimal level of proactive investments in learning.     

Single machine scheduling with exponential learning functions

In this paper we consider the single machine scheduling problem with exponential learning functions. By the exponential learning functions, we mean that the actual job processing time is a function of the total normal processing times of the jobs already processed. We prove that the shortest processing time (SPT) rule is optimal for the total lateness minimization problem. For the following three objective functions, the total weighted completion time, the discounted total weighted completion time, the maximum lateness, we present heuristic algorithms according to the corresponding problems without exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms. It also shows that the problems of minimizing the total tardiness and discounted total weighted completion time are polynomially solvable under some agreeable conditions on the problem parameters.     

Scheduling jobs with truncated exponential learning functions

In this paper we consider the single machine scheduling problem with truncated exponential learning functions. By the truncated exponential learning functions, we mean that the actual job processing time is a function which depends not only on the total normal processing times of the jobs already processed but also on a control parameter. The use of the truncated function is to model the phenomenon that the learning of a human activity is limited. We show that even with the introduction of the proposed model to job processing times, several single machine problems remain polynomially solvable. For the following three objective functions, the total weighted completion time, the discounted total weighted completion time, the maximum lateness, we present heuristic algorithms according to the corresponding problems without truncated exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms.     

基于相近原则的半指导直推学习机及其增量算法

半指导问题是近来机器学习研究中的备受关注一个重要内容．本文以满足“在输入空间中相近的对象其输出也相近”这一源于直观事实的原则(相近原则)去解决半指导学习问题,给出在这个原则下的一个一般的直接推理方法—基于相近原则的半指导问题直推学习机,得到了这个问题的解析解及迭代算法,用模式分类实例验证该方法的有效性,并给出适于在线处理的增量学习算法,这些增量算法尤其还适于新增了有指导的信息的场合．     

Complexity results for single-machine scheduling with positional learning effects

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.     

带准备时间的单机指数时间学习效应排序问题

研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。     

Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect

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.     

Single machine scheduling with a general exponential learning effect

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.     

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

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

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.     

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 bicriteria parallel machine scheduling with a learning effect of setup and removal times

In studies on scheduling problems, generally setup times and removal times of jobs have been neglected or by including those into processing times. However, in some production systems, setup times and removal times are very important such that they should be considered independent from processing times. Since, in general jobs are done according to automatic machine processes in production systems processing times do not differ according to process sequence. But, since human factor becomes influential when setup times and removal times are taken into consideration, setup times will be decreasing by repeating setup processes frequently. This fact is defined with learning effect in scheduling literature. In this study, a bicriteria m-identical parallel machines scheduling problem with a learning effect of setup times and removal times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. A mathematical programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 15 jobs and five machines. We also proposed three heuristic approaches for solving large jobs problems. According to the best of our knowledge, no work exists on the minimization of the weighted sum of total completion time and total tardiness with a learning effect of setup times and removal times.     

Two-agent scheduling with position-based deteriorating jobs and learning effects

Scheduling with deteriorating jobs and learning effects has been widely studied. However, multi-agent scheduling with simultaneous considerations of deteriorating jobs and learning effects has hardly been considered until now. In view of this, we consider a two-agent single-machine scheduling problem involving deteriorating jobs and learning effects simultaneously. In the proposed model, given a schedule, we assume that the actual processing time of a job of the first agent is a function of position-based learning while the actual processing time of a job of the second agent is a function of position-based deterioration. The objective is to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We develop a branch-and-bound and several simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.     

Computational complexity of the single processor makespan minimization problem with release dates and job-dependent learning

In this paper, we analyse the single processor maximum completion time (makespan) minimization problem with distinct release dates of jobs and the sum-of-processing time-based learning effect. We prove that the considered problem is strongly NP-hard, if, in addition to jobs with the same learning ratio, there are jobs with constant job processing times. Such jobs are not affected by learning and model, for instance, required system upgrades or training courses.