One-machine scheduling problems with deteriorating jobs and position-dependent learning effects under group technology considerations

In this paper, we introduce a group scheduling model with general deteriorating jobs and learning effects in which deteriorating jobs and learning effects are both considered simultaneously. This means that the actual processing time of a job depends not only on the processing time of the jobs already processed, but also on its scheduled position. In our model, the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent learning effects and time-dependent deterioration. The objective of scheduling problems is to minimise the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model.     

Single-machine scheduling with learning effect and deteriorating jobs

In this paper we consider the single-machine scheduling problems with the effects of learning and deterioration. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single machine makespan and sum of completion times (square) minimization problems remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively.     

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

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

Flowshop scheduling with a general exponential learning effect

This paper investigates flowshop scheduling problems with a general exponential learning effect, i.e., the actual 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 objective is to minimize the makespan, the total (weighted) completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times, respectively. Several simple heuristic algorithms are proposed in this paper by using the optimal schedules for the corresponding single machine problems. The tight worst-case bound of these heuristic algorithms is also given. Two well-known heuristics are also proposed for the flowshop scheduling with a general exponential learning effect.     

Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times

The single-machine scheduling problem with truncated sum-of-processing-times-based learning effect and past-sequence-dependent job delivery times is considered. Each job’s delivery time depends on its waiting time of processing. For some regular objective functions, it is proved that the problems can be solved by the smallest processing time first rule. For some special cases of the total weighted completion time and the maximum lateness objective functions, the thesis shows that the problems can be solved in polynomial time.     

Several flow shop scheduling problems with truncated position-based learning effect

The concept of truncated position-based learning process plays a key role in production environments. However, it is relatively unexplored in the flow shop setting. In this paper, we consider the flow shop scheduling with truncated position-based learning effect, i.e., the actual processing time of a job is a function of its position and a control parameter in a processing permutation. The objective is to minimize one of the six regular performance criteria, namely, the total completion time, the makespan, the total weighted completion time, the discounted total weighted completion time, the sum of the quadratic job completion times, and the maximum lateness. We present heuristic algorithms and analyze the worst-case bound of these heuristic algorithms. We also provide the computational results to evaluate the performance of the heuristics.     

Single-machine scheduling jobs with exponential learning functions

In a manufacturing system workers are involved in doing the same job or activity repeatedly. Hence, the workers start learning more about the job or activity. Because of the learning, the time to complete the job or activity starts decreasing, which is known as “learning effect”. In this paper, an exponential sum-of-actual-processing-time based learning effect is introduced into single-machine scheduling. By the exponential sum-of-actual-processing-time based learning effect, we mean that the processing time of a job is defined by an exponential function of the sum-of-the-actual-processing-time of the already processed jobs. Under the proposed learning model, we show that under a sufficient condition, the makespan minimization problem, the sum of the θth (θ > 0) power of completion times minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem remain polynomially solvable.     

Single-machine scheduling problems with deteriorating jobs and learning effects

In this paper, we introduce a new scheduling model in which deteriorating jobs and learning effect are both considered simultaneously. By deterioration and the learning effect, we mean that the actual processing time of a job depends not only on the processing time of the jobs already processed but also on its scheduled position. For the single-machine case, we show that the problems of makespan, total completion time and the sum of the quadratic job completion times remain polynomially solvable, respectively. In addition,we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain conditions.     

Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects

In traditional scheduling problems, the processing time for the given job is assumed to be a constant regardless of whether the job is scheduled earlier or later. However, the phenomenon named “learning effect” has extensively been studied recently, in which job processing times decline as workers gain more experience. This paper discusses a bi-criteria scheduling problem in an m-machine permutation flowshop environment with varied learning effects on different machines. The objective of this paper is to minimize the weighted sum of the total completion time and the makespan. A dominance criterion and a lower bound are proposed to accelerate the branch-and-bound algorithm for deriving the optimal solution. In addition, the near-optimal solutions are derived by adapting two well-known heuristic algorithms. The computational experiments reveal that the proposed branch-and-bound algorithm can effectively deal with problems with up to 16 jobs, and the proposed heuristic algorithms can yield accurate near-optimal solutions.     

A Truncated Sum of Processing‐Times–Based Learning Model for a Two‐Machine Flowshop Scheduling Problem

Scheduling with learning effects has gained increasing attention in recent years. A well‐known learning model is called “sum‐of‐processing‐times‐based learning” in which the actual processing time of a job is a nonincreasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Moreover, the concept of learning process is relatively unexplored in a flowshop environment. Motivated by these observations, this article addresses a two‐machine flowshop problem with a truncated learning effect. The objective is to find an optimal schedule to minimize the total completion time. First, a branch‐and‐bound algorithm incorporating with a dominance property and four lower bounds is developed to derive the optimal solution. Then three simulated annealing algorithms are also proposed for near‐optimal solution. The experimental results indicated that the branch‐and‐bound algorithm can solve instances up to 18 jobs, and the proposed simulated annealing algorithm performs well in item of CPU time and error percentage. © 2011 Wiley Periodicals, Inc.     

Single-machine scheduling with learning effect and resource-dependent processing times

We consider resource allocation scheduling with learning effect in which the processing time of a job is a function of its position in a sequence and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We analyse the problem with two different processing time functions. For each combination of these, we provide a polynomial time algorithm to find the optimal job sequence and resource allocation.     

Single-machine group scheduling with resource allocation and learning effect

This paper addresses single-machine scheduling problems under the consideration of learning effect and resource allocation in a group technology environment. In the proposed model of this paper the actual processing times of jobs depend on the job position, the group position, and the amount of resource allocated to them concurrently. Learning effect and two resource allocation functions are examined for minimizing the weighted sum of makespan and total resource cost, and the weighted sum of total completion time and total resource cost. We show that the problems for minimizing the weighted sum of makespan and total resource cost remain polynomially solvable. We also prove that the problems for minimizing the weighted sum of total completion time and total resource cost have polynomial solutions under certain conditions.     

Single machine scheduling with past-sequence-dependent setup times and learning effects

This paper studies a single machine scheduling problem with setup times and learning considerations. The setup times are proportional to the length of the already scheduled jobs. That is, the setup times are past-sequence-dependent. It is assumed that the learning process reflects a decrease in the process time as a function of the number of repetitions, i.e., as a function of the job position in the sequence. The following objectives are considered: the makespan, the total completion time, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalty. Polynomial time algorithms are proposed to optimally solve the above objective functions.     

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

Scheduling with learning effects has attracted growing attention of the scheduling research community. A recent survey classifies the learning models in scheduling into two types, namely position-based learning and sum-of-processing-times-based learning. However, the actual processing time of a given job drops to zero precipitously as the number of jobs increases in the first model and when the normal job processing times are large in the second model. Motivated by this observation, we propose a new learning model where the actual job processing time is a function of the sum of the logarithm of the processing times of the jobs already processed. The use of the logarithm function is to model the phenomenon that learning as a human activity is subject to the law of diminishing return. Under the proposed learning model, we show that the scheduling problems to minimize the makespan and total completion time can be solved in polynomial time. We further show that the problems to minimize the maximum lateness, maximum tardiness, weighted sum of completion times and total tardiness have polynomial-time solutions under some agreeable conditions on the problem parameters.     

On scheduling a single machine with resource dependent release times

We consider a single machine scheduling problem with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. The objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. It is known that the problem is polynomially solvable in O(n⁴) with n the number of jobs.     

Single machine scheduling problems with resource dependent release times

We consider two single machine scheduling problems with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. In the first problem, the objective is to minimize the total resource consumption with a constraint on the sum of job completion times. We show that a recognition version of the problem is NP-complete. In the second problem, the objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. We provide some optimality conditions and show that the problem is polynomially solvable.     

A note on scheduling problems with learning effect and deteriorating jobs

In this note, we consider the machine scheduling problems with the effects of deterioration and learning. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The scheduling objectives are makespan (weighted) sum of completion times and maximum lateness. It is shown that even with the introduction of deterioration and learning effect to job processing times, several single machine problems and several flow shop problems remain polynomially solvable, respectively.     

Total absolute deviation of job completion times on uniform and unrelated machines

Unlike other measures of variation of job completion times considered in scheduling literature, the measure of minimizing total absolute deviation of job completiontimes (TADC) was shown to have a polynomial time solution on a single machine. It was recently shown to remain polynomially solvable when position-dependent job processing times are assumed. In this paper we further extend these results, and show that minimizing TADC remains polynomial when position-dependent processing times are assumed (i) on uniform and unrelated machines and (ii) for a bicriteria objective consisting of a linear combination of total job completion times and TADC. These extensions are shown to be valid also for the measure of total absolute differences of job waiting times (TADW).     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.