Single-machine and two-machine flowshop scheduling with general learning functions

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.     

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

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.     

Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects

This paper studies the single machine past-sequence-dependent (p-s-d) delivery times scheduling with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. We consider the following objective functions: the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?0$) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of minimization of the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?0$) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, the maximum tardiness minimization problem and the total tardiness 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.     

Single-machine batch scheduling minimizing weighted flow times and delivery costs

This paper addresses scheduling a set of jobs on a single machine for delivery in batches to one customer or to another machine for further processing. The problem is a natural extension of that of minimising the sum of weighted flow times, considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimising the sum of weighted flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution method. For the special case, when the maximum number of batches is fixed, the branch-and-bound scheme provided shows significant improvements over an existing dynamic-programming algorithm.     

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 deteriorating functions for job processing times

In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier – this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions.     

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 problems with both deteriorating jobs and learning effects

In this paper we consider the single-machine scheduling problems with job-position-based and sum-of-processing-times based processing times. The real processing time of a job is a function of its position and the total processing time of the jobs that are in front of it in the sequence. The objective is to minimize the makespan, and to minimize the mean finish time. We prove that some special cases are polynomially solvable under some restrictions of the parameters. In addition, for some another special cases of minimization of the mean finish time and the makespan, we show that an optimal schedule is V-shaped with respect to job normal processing times. Then, we propose a heuristic based on the V-shaped property, and show through a computational experiment that it performs efficiently.     

Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect

This paper considers identical parallel-machine scheduling problem with past-sequence-dependent (psd) delivery times and learning effect. In electronic manufacturing industry, an electronic component may be exposed to certain electromagnetic field and requires an extra time for eliminating adverse effect after the main processing. The extra time is modeled as past-sequence-dependent delivery time in the literature, which is proportional to the waiting time in the system. It is also observed that the learning process reflects a decrease in the processing time as a function of the number of repetitions, i.e., as a function of the job position in the sequence. In practice, one often has to deal with the scheduling problems with psd delivery times and learning effect. Identical parallel-machine setting is considered because the occurrence of resources in parallel is common in the real world. In this paper, three objectives are the minimization of the total absolute deviation of job completion times, the total load on all machines and the total completion time. We develop polynomial algorithms to optimally solve these problems.     

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.     

Single-machine scheduling problems with actual time-dependent and job-dependent learning effect

In this study, we introduce an actual time-dependent and job-dependent learning effect into single-machine scheduling problems. We show that the complexity results of the makespan minimization problem and the sum of weighted completion time minimization problem are all NP-hard. The complexity result of the maximum lateness minimization problem is NP-hard in the strong sense. We also provide three special cases which can be solved by polynomial time algorithms.     

Single-machine scheduling with waiting-time-dependent due dates

We consider a single-machine scheduling problem in which due dates are linear functions of the job waiting-times and the objective is to minimize the maximum lateness. An optimal sequence is constructed by implementing an index-based priority rule for a fixed value of the due date normalizing constant k. We determine in polynomial time all the k value ranges so that the optimal sequence remains the same within each range. The optimal due dates are computed as linear functions of the global optimal value of k. The overall procedure is illustrated in a numerical example.     

Single-machine scheduling problems with an actual time-dependent deterioration

In this paper, we consider the single machine scheduling problems with an actual time-dependent deterioration effect. By the actual time-dependent deterioration effect, we mean that the processing time of a job is defined by increasing function of total actual processing time of jobs in front of it in the sequence. We show that even with the introduction of an actual time-dependent deterioration to job processing times, makespan minimization problem, total completion time minimization problem, the total lateness, and the sum of the quadratic job completion times minimization problem remain polynomially solvable, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, and the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

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

Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning

In this paper we consider the single-machine setup times scheduling with general effects of deterioration and learning. By the general effects of deterioration and learning, we mean that the actual job processing time is a general function of the processing times of the jobs already processed and its scheduled position. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We show that the problems to minimize the makespan, the sum of the δ$\delta$th (δ>0$\delta >0$) power of job completion times, the total lateness are polynomially solvable. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness (tardiness) minimization problem, the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration

In this paper we introduce a new model of joint start-time dependent learning and position dependent aging effects into single-machine scheduling problems. The machine may need maintenance to improve its production efficiency. The objectives are to find jointly the optimal maintenance position and the optimal sequence such that the makespan, the total completion time, and the total absolute deviation of completion times (TADC) are minimized. We also aim to determine jointly the optimal maintenance position, the optimal due-window size and location, and the optimal sequence to minimize the sum of earliness, tardiness and due-window related costs function. We show that all the studied problems can be optimally solved by polynomial time algorithms.