Scheduling with Learning and Forgetting Effects

Single-machine schedulingwith learning effects in intermittent batchproduction

Dar-Li Yang and Wen-Hung Kuo[＊]

Department of Information Management,

NationalFormosaUniversity,

Yun-Lin, Taiwan 632, R.O.C.

Abstract

Keywords: single-machine; scheduling; intermittent; learning; makespan

1. Introduction

In classical scheduling problems, processing times of jobs are assumed to be constant. However, in many realistic situations, because the firms and employees perform the same task repeatedly, they learn how to perform more efficiently. Therefore, the actual processing time of a job is shorter when it is scheduled later, rather than earlier in the sequence. This phenomenon is known as the “learning effect” in the literature.

Biskup [1]first proposed a learning effect model in which the processing time of a job is a function of the job position in a sequence. He showed that single-machine scheduling problems with a learning effect still remain polynomially solvable if the objective is to minimize the deviation from a common due date or to minimize the sum of flow times. Mosheiov [2]provideda polynomial time solution for the single-machine makespan minimization problem and solved two multi-criteria problems which can be formulated as assignment problems. He also showed that the SPT (the shortest processing time first) rule does not remain optimal for the minimum flow-time problem on parallel identical machines. Mosheiov [3] further showed that the flow-time minimization problem with the learning effect on parallel identical machines has a solution which is polynomial in the number of jobs. Mosheiov and Sidney [4] extended learning effect to be job-dependent, that is, learning rates are different from job to job. They showed that the problems of makespan and total flow-time minimization on a single machine, a due-date assignment problem and total flow-time minimization on unrelated parallel machines remain polynomially solvable.

The above learning effect models tell us that, as cumulative jobs increase, the processing time of the following job decreases in a continuous production system. It gives the implication of continuous rather than intermittent batch production. However, the pattern of many realistic production systems is intermittent. There is a setup between two production runs. In such intermittent production, it is reasonable to assume that if a large amount of time has elapsed between production runs, the learning effect would not continue to follow what it was left when production resumes, but that the processing time of the following job would revert to a higher level. This suggests a phenomenon of forgetting between production runs. That is, there may be only partial or even no transmission of learning from one production run to another one.Hence, it is clear that this problem of learning and forgetting is an interesting topic for intermittent production.

2. Notations and assumptions

As mentioned above, we consider a single-machine scheduling problem with learning and forgetting effects in intermittent batch production. The problem is developed using the following notations. Additional notations will be introduced when needed throughout the paper.

m : the number of batches. ()

: the ith batch, i=1, 2, …, m.

: the number of jobs in batch , i=1, 2, …, m.

n : the total number of jobs. (i.e. )

: thejth job in batch, j=1, 2, …, .

: the batch setup time of batch

: the learning factor of jobs within batch . ()

: the learning factor of batch . ()

: the normal processing time of in the original sequence.

: the actual processing time of which is scheduled in the r th position

in a sequence in batch.

: the normal processing time of which is scheduled in the k th position

in a sequence in batch.

: the actual processing time of which is scheduled in the k th position

in a sequence in batch.

: the completion time of

: the completion time of which is scheduled in the k th position

in a sequence in batch.

: the makespan of all jobs.

There are n jobs grouped into mbatches and processed on a single machine. All jobs are available at time zero. Assume that there is no setup time between two consecutive jobs in the same batch. However, a setup time is required to process a batch anditis sequence-independent.Moreover, the normal processing time of a job is incurred if the job is scheduled first in the first production batch. The actual processing times of the following jobs are smaller than their normal processing times because of the learning effect.Assume that the actual processing time of a job is a decreasing function of its position in a sequence. Usually, the learning effect can be accumulated through completing jobs. However, if a large amount of setup time has elapsed between production runs, it may incur a forgetting effect.That is, there may be partial or even no transmission of learning from batch to batch. Therefore, three models of learning and forgetting effects are considered in the following.

3. Model I: No transmission of learning from batch to batch

In the first model, we consider that there is no transmission of learning from batch to batch. The objective of the single-machine scheduling problem is to minimize the makespan of all jobs. As mentioned in Biskup [1], we assume that the actual processing time of job when scheduled in position r in batch , is given by

Hence, the makespan of all jobs is as follows:

For convenience, let LE denote the learning effect and S denote the existence of a sequence-independent batch setup time. In addition, let B denote that the problem is an intermittent batch production problem and denote that there is no transmission of learning from batch to batch. Therefore, followingthe three-field notation of Graham et al. [5], the proposed problem is denoted by .

Theorem 1. For the problem of , there exists an optimal schedule that satisfies the following conditions: (a) the jobs within a batch are sequenced in non-decreasing order of their normal processing time.(b) the batches can be sequenced in any order.

Proof. The problem to arrange the job sequence within a batch is the same as the problem of . Mosheiov [2] proved that the optimal schedule is to sequence the jobs in non-decreasing order of their normal processing time. Therefore, the theorem follows because there is no transmission of learning from batch to batch and the batch setup is sequence-independent. □

Based on Theorem 1, a simple algorithm to determine the optimal schedule for the problem of is developed as follow.

Algorithm 1.

Step 1: Arrange jobs within each batch in non-decreasing order of their normal processing times.

Step 2: Batches are scheduled in any order.

The optimal job sequence within a certain batch can be obtained by a sorting algorithm andthustaking time. Hence, the total running time to sequence jobs of all batches is . On the other hand, the running time to sequence the batches in any order is .Therefore, the overall complexity of theproblem of is(see Kuo and Yang [8]).

4. Model II: Partial transmission of learning from batch to batch

In the second model, we consider partial transmission of learning from batch to batch in the single-machine scheduling problem. Therefore, there exists some learning effect between batches besides the learning effect within a batch. We assume that the learning effect of jobs within a batch is the same as that in the first model. In addition, the actual processing time of batchwhen scheduled in the rth batch is defined as follows.

where is the total processing time of jobs within batch if there is no transmission of learning from batch to batch. That is, .

Then, the makespan of all jobs is calculated as follows:

(1)

Let denote that there is only partial transmission of learning from batch to batch. Then the proposed problem is denoted by . As in Biskup [1], let be a 0/1 variable such that = 1 if batch is the rth batch to be processed and = 0 otherwise. Then the problem of can be formulated as the following assignment problem.

min

s.t. , r =1, 2, …, m,

, i =1, 2, …, m,

or 1, i, r =1, 2, …, m. (2)

Since of batch is not affected by the batch sequence, from Theorem 1, can be minimized by sequencing the corresponding jobs in non-decreasing order of their normal processing time. Based on the above analysis, a simple algorithm to determine the optimal schedule for the problem of is developed as follow.

Algorithm 2.

Step 1: Arrange jobs within each batch in non-decreasing order of their normal processing times.

Step 2: Formulate the corresponding assignment problem as Eq.(2) and determine the batch sequence according to the solution of the corresponding problem.

From the analysis in Section 3, the complexity of Step 1 is . On the other hand, Step 2 is to solve an assignment problem and thus the complexity of Step 2 is. Thus, the overall complexity of Algorithm 2 is .

Corollary 1. If the learning factors of all batches are equal, i.e. , then for the problem of , there exists an optimal schedule that satisfies the following conditions: (a) the jobs within a batch are sequenced in non-decreasing order of their normal processing time. (b) the batches are sequenced in non-decreasing order of .

Proof.As stated in Theorem 1, the problem to arrange the job sequence within a batch is the same as the problem of . Mosheiov [2] proved that the optimal schedule is to sequence the jobs in non-decreasing order of their normal processing time. In addition, the term of in Eq.(1) is constant. Therefore, to minimize the makespan of all jobs is equal to minimizing the term ofin Eq.(1). Because ,to minimize is equivalent to minimizing the makespan of the problem of if batches are taken as jobs. Then, the result in part (b) of Corollary 1 follows. □

From Corollary 1, if , the complexity of the problem of is reduced to .

5. Model III: Total transmission of learning from batch to batch

In the third model, we consider total transmission of learning from batch to batch in the single-machine scheduling problem. Without loss of generality, assume that batch is sequenced in the ith batch. Then, the actual processing time of job when scheduled in position r in batch is as follows.

Hence, the makespan of all jobs is calculated as follows.

Let denote total transmission of learning from batch to batch. Then the proposed problem is denoted by .

Theorem 2. For any batch sequence of the problem, the total processing time of jobs within the batch is minimized by sequencing jobs in non-decreasing order of their normal processing time.

Proof. The theorem can be easily proved by using simple job interchanging technique. □

Corollary2. For the problem of , there exists an optimal schedule by sequencing jobs within each batch in non-decreasing order of their normal processing time.

Proof. The result follows directly from Theorem 2. □

In the following, two special cases of the problem of are discussed in Theorem 3 and Algorithm 3, respectively.

Definition 1. is dominated by , or dominates iff . The symbol denotes that is dominated by .

Definition 2. The batches form an increasing sequence of dominating batches iff .

Theorem 3.If and , then for the problem of , there exists an optimal schedule satisfies the following conditions.

(a) the jobs within a batch are sequenced in non-decreasing order of their normal processing time.

(b) the batches are arranged as an increasing sequence of dominating batches.

Proof. The theorem can be easily proved by using simple job interchanging technique. □

Next,if the job numbers of all batches are equal (i.e. ), then the proposed problem can be formulated as an assignment problem. Again, let be a 0/1 variable such that = 1 if batch is the rth batch to be processed and = 0 otherwise. Then, the problem to minimize the makespan of all jobs is formulated as follows.

min

s.t. , r =1, 2, …, m,

, i =1, 2, …, m,

or 1, i, r =1, 2, …, m. (3)

Based on Theorem 2 and the above analysis, to determine the optimal schedule for the problem of , a similar algorithmas Algorithm 2 is developed as follow.

Algorithm 3.

Step 1: Arrange jobs within each batch in non-decreasing order of their normal processing times.

Step 2: Formulate the corresponding assignment problem as Eq.(3) and determine the batch sequence according to the solution of the corresponding problem.

Note that Step 1 can be obtained by a sorting algorithm and thus it takes time while Step 2 is to solve an assignment problem and thus it takes time. Thus, the overall time complexity of Algorithm 3 is .

6. Conclusions

This paper studiesa single-machine scheduling problem with three models of learning and forgetting effects in intermittent batch production. They are the models of no transmission, partial transmission and total transmission of learning from batch to batch, respectively. The objective is to minimize the makespan. We provide a polynomial time algorithm to solve the problems with the models of no transmission andpartial transmission of learningfrom batch to batch, respectively. We also provide twopolynomial time algorithms to find the optimal solutions of two special cases in the problem with the model of total transmission of learning from batch to batch. However, the complexity of the problem with the model of total transmission of learning from batch to batch is an open question. Therefore, it is an interesting topic for the future research. Besides, in this study,the learning effect of a job depends on its position in a schedule. There are other learning effect models studied in the literature [6,7]. Thus, it is also worthwhile to consider another learning effect model in intermittent batch production, for example, a time-dependent learning effect model proposed by Kuo and Yang [8,9].

Acknowledgements

This research is supported in part by the National Science Council of Taiwan, Republic of China, under grant number NSC-94-2213-E-150-016.

References

1. Biskup D (1999). Single-machine scheduling with learning considerations. Eur J Opl Res115: 173-178.

2. Mosheiov G (2001a). Scheduling problems with learning effect. Eur J Opl Res132: 687-693.

3. Mosheiov G (2001b). Parallel machine scheduling with learning effect. J Opl Res Soc52: 1-5.

4. Mosheiov G and Sidney JB (2003). Scheduling with general job-dependent learning curves. Eur J Opl Res 147: 665-670.

5. Graham RL, Lawler EL, Lenstra JK, RinnooyKan AHG. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals Discrete Mathematics 5: 287-326.

6. Alidaee B, Womer NK (1990). Scheduling with time dependent processing times: Review and extensions. J Opl Res Soc 50: 711-729.

7. Cheng TCE, Ding Q, Lin BMT (2004). A concise survey of scheduling with time-dependent processing times. Eur J Opl Res152: 1-13.

8. Kuo WH, Yang DL (2006). Single-machine group scheduling with a time-dependent learning effect. Comput Opns Res33(8): 2099-2112.

9. Kuo WH, Yang DL (2006).Minimizing the total completion time in a single machine scheduling problem with a time-dependent learning effect. Eur J Opl Res174(2): 1184-1190.

[＊]Correspondence: WH Kuo, Department of Information Management , NationalFormosaUniversity, Yun-Lin, Taiwan 632, ROC.

E-mail address: