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.     

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 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.     

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.     

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.     

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.     

A note on single-machine scheduling with job-dependent learning effects

Mosheiov and Sidney (2003) showed that the makespan minimization problem with job-dependent learning effects can be formulated as an assignment problem and solved in O(n³) time. We show that this problem can be solved in O(nlog n) time by sequencing the jobs according to the shortest processing time (SPT) order if we utilize the observation that the job-dependent learning rates are correlated with the level of sophistication of the jobs and assume that these rates are bounded from below. The optimality of the SPT sequence is also preserved when the job-dependent learning rates are inversely correlated with the level of sophistication of the jobs and bounded from above.     

Notes on “A bicriteria flowshop scheduling with a learning effect”

The aim of this paper is to point out that the integer programming model proposed by Eren and Güner [T. Eren, E. Güner, A bicriteria flowshop scheduling with a learning effect, Applied Mathematical Modelling 32 (2008) 1719–1733] is incorrect. We propose a mixed 0–1 programming model for the same scheduling problem based on their model.     

Comments on “A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect”

The purpose of this paper is to point out that if there are some machines that do not process any job then the mathematical programming model provided by Eren [T. Eren, A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect, Applied Mathematics and Computation 209 (2009) 186-190] may not be a valid one. A simple way to fix this problem is given. Furthermore, based on the idea of Eren’s model, a general mathematical programming model is proposed.     

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 scheduling problems with time-dependent learning effect and deteriorating jobs

Although machine scheduling problems with learning and deteriorating effects consideration have received increasing attention in the recent years, most studies have seldom considered the two phenomena simultaneously. However, learning and deteriorating effects might co-exist in many realistic scheduling situations. Thus, in this article, a model which takes the effects of time-dependent learning and deterioration simultaneously is proposed and applied into some scheduling problems. Under the proposed model, the processing time of a job is determined by a function of its corresponding starting time and positional sequence in each machine. We show that some single machine and flowshop scheduling problems are polynomially solvable with the certain performance measures such as makespan, total completion time, and weighted completion time.     

基于加工时间之和学习效应下的单机成组排序问题

研究具有加工时间之和学习效应下的一个新型成组排序问题,工件的学习效应是之前工件加工时间之和的函数,组学习效应是成组加工所在的位置的函数. 考虑最大完工时间和总完工时间两个问题,证明了这两个问题都是多项式时间可解的,并提出了相应的多项式时间算法.     

Comments on “A bicriteria parallel machine scheduling with a learning effect of setup and removal times”

The purpose of this paper is to point out some errors in Eren [Applied Mathematical Modelling, 33 (2009) 1141–1150]. We also suggest some methods to fix them.     

A note on single-machine scheduling with decreasing time-dependent job processing times

In this note we consider some single-machine scheduling problems with decreasing time-dependent job processing times. Decreasing time-dependent job processing times means that its processing time is a non-increasing function of its execution start time. We present polynomial solutions for the sum of squared completion times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs, respectively. We also study two resource constrained scheduling problems under the same decreasing time-dependent job processing times model and present algorithms to find their optimal solutions.     

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.     

Single-machine scheduling with learning and forgetting effects

Scheduling with learning effects has been widely studied in the past decade. With the increasingly moving toward shorter product cycle times in many production lines, workers in this changeable environment must constantly learn new skill and technology. As a result, the forgetting effect might occur in these situations. In this paper, we propose a model with the consideration of both the learning and forgetting effects. We show some single-machine problems remain polynomially solvable under the proposed model.     

Learning and forgetting effects on a group scheduling problem

This paper proposes to investigate learning and forgetting effects on the problem of scheduling families of jobs on a single machine to minimize total completion time of jobs. A setup time is incurred whenever the single machine transfers job processing from a family to another family. To analyze the impact of learning and forgetting on this group scheduling problem, we structure three basic models and make some comparisons through computational experiments. The three models, including no forgetting, total forgetting and partial forgetting, assume that the processing time of a job is dependent on its position in a schedule. Some scheduling rules and a lower bound are derived in order to constitute our branch-and-bound algorithm for searching an optimal sequence. In addition, an efficient and simply-structured heuristic is also built to find a near-optimal schedule.     

Single-machine group scheduling with processing times dependent on position,starting time and allotted resource

This article considers scheduling problems on a single machine with learning effect, deteriorating jobs and resource allocation under group technology (GT) assumption. We assume that the actual processing time of a job depends on the job position, the group position, the starting time and the amount of resource allocated to them concurrently, and the actual setup times of groups depend on the group position and the amount of resource allocated to them concurrently. Two resource allocation functions are examined for minimizing the weighted sum of makespan and total resource cost. We prove that the problems have polynomial solutions under the condition that the number of jobs in each group are the same.     

Single-machine scheduling with effects of exponential learning and general deterioration

The purpose of this study is to explore the single-machine scheduling with the effects of exponential learning and general deterioration. By the effects of exponential learning and general deterioration, we meant that job processing time is decided by the functions of their starting time and positions in the sequence. Results showed that with the introduction of learning effect and deteriorating jobs to job processing time, single-machine makespan, and sum of completion time (square) minimization problems remained polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion time and the maximum lateness, this paper proved that the weighted smallest basic processing time first (WSPT) rule and the earliest due date first (EDD) rule constructed the optimal sequence under some special cases, respectively.     

A bicriteria flowshop scheduling with a learning effect

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n² + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect.