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.     

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 and flowshop scheduling with a general learning effect model

Learning effects in scheduling problems have received growing attention recently. Biskup [Biskup, D. (2008). A state-of-the-art review on scheduling with learning effect. European Journal of Operational Research, 188, 315–329] classified the learning effect scheduling models into two diverse approaches. The position-based learning model seems to be a realistic assumption for the case that the actual processing of the job is mainly machine driven, while the sum-of-processing-time-based learning model takes into account the experience the workers gain from producing the jobs. In this paper, we propose a learning model which considers both the machine and human learning effects simultaneously. We first show that the position-based learning and the sum-of-processing-time-based learning models in the literature are special cases of the proposed model. Moreover, we present the solution procedures for some single-machine and some flowshop problems.     

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.     

Note on “Single-machine and flowshop scheduling with a general learning effect model” and “Some single-machine and m-machine flowshop scheduling problems with learning considerations”

In this note, we show that the main results in the two papers [C.C. Wu, W.C. Lee, Single-machine and flowshop scheduling with a general learning effect model, Computers and Industrial Engineering 56 (2009) 1553-1558, W.C. Lee, C.C. Wu, Some single-machine and m-machine flowshop scheduling problems with learning considerations, Information Sciences 179 (2009) 3885-3892] are incorrect.     

Two-agent scheduling with learning consideration

In traditional scheduling, job processing times are assumed to be known and fixed over the entire process. However, repeated processing of similar tasks improves workers’ skills. In fact, scheduling with learning effects has received considerable attention recently. On the other hand, it is assumed that there is a common objective for all the jobs. In many management situations, multiple agents pursuing different objectives compete on the usage of a common processing resource. In this paper, we studied a single-machine two-agent scheduling problem with learning effects where the objective is to minimize the total tardiness of jobs from the first agent given that no tardy job is allowed for the second agent. A branch-and-bound algorithm incorporated several properties and a lower bound is developed to search for the optimal solution. In addition, two heuristic algorithms are also proposed to search for the near-optimal solutions. A computational experiment is conducted to evaluate the performance of the proposed algorithms.     

Single-machine group scheduling with both learning effects and deteriorating jobs

In the paper two resource constrained single-machine group scheduling problems with both learning effects and deteriorating jobs are considered. By learning effects, deteriorating jobs and group technology assumption, we mean that the processing time of a job is defined by the function of its starting time and position in the group, and the group setup times of a group is a positive strictly decreasing continuous function of the amount of consumed resource. We present polynomial solutions for the makespan minimization problem under the constraint that the total resource consumption does not exceed a given limit, and the total resource consumption minimization problem under the constraint that the makespan does not exceed a given limit, respectively.     

Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects

In this paper we introduce a new scheduling model with learning effects in which the actual processing time of a job is a function of the total normal processing times of the jobs already processed and of the job’s scheduled position. We show that the single-machine problems to minimize makespan and total completion time are polynomially solvable. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. Finally, we present polynomial-time optimal solutions for some special cases of the m-machine flowshop problems to minimize makespan and total completion time.     

Some single-machine and m-machine flowshop scheduling problems with learning considerations

Scheduling with learning effect has drawn many researchers’ attention since Biskup [D. Biskup, Single-machine scheduling with learning considerations, European Journal of Opterational Research 115 (1999) 173-178] introduced the concept of learning into the scheduling field. Biskup [D. Biskup, A state-of-the-art review on scheduling with learning effect, European Journal of Opterational Research 188 (2008) 315-329] classified the learning approaches in the literature into two main streams. He claimed that the position-based learning seems to be a realistic model for machine learning, while the sum-of-processing-time-based learning is a model for human learning. In some realistic situations, both the machine and human learning might exist simultaneously. For example, robots with neural networks are used in computers, motor vehicles, and many assembly lines. The actions of a robot are constantly modified through self-learning in processing the jobs. On the other hand, the operators in the control center learn how to give the commands efficiently through working experience. In this paper, we propose a new learning model that unifies the two main approaches. We show that some single-machine problems and some specified flowshop problems are polynomially solvable.     

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 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 a nonlinear deterioration function

In deteriorating job scheduling problems, most of the researchers assume that the actual job processing time is a function of its starting time. In this paper, we propose a new deterioration model in which the actual job processing time is a general function of the normal processing time of jobs already processed and its scheduled position at the same time. We show that some single-machine scheduling problems remain polynomially solvable.     

The single-machine total weighted tardiness scheduling problem with position-based learning effects

This study addresses the problem of minimizing the total weighted tardiness on a single-machine with a position-based learning effect. Several dominance properties are established to develop branch and bound algorithm and a lower bound is provided to derive the optimal solution. In addition, three heuristic procedures are developed for near-optimal solutions. Computational results are also presented to evaluate the performance of the proposed algorithms.     

A note on single-machine scheduling with general learning effect and past-sequence-dependent setup time

In this paper, we study a scheduling model with the consideration of both the learning effect and the setup time. Under the proposed model, the learning effect is a general function of the processing time of jobs already processed and its scheduled position, and the setup time is past-sequence-dependent. We then derive the optimal sequences for two single-machine problems, which are the makespan and the total completion time. Moreover, we showed that the weighted completion time, the maximum lateness, the maximum tardiness, and the total tardiness problems remain polynomially solvable under agreeable conditions.     

Some scheduling problems with general position-dependent and time-dependent learning effects

In scheduling problems with learning effects, most of the research is based on specific learning functions. In this paper, we develop a general model with learning effects where 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. In particular, it is shown that some single machine scheduling problems and m-machine permutation flowshop problems are still polynomially solvable under the proposed model. These results are significant extensions of some of the existing results on learning effects in the literature.     

Solving a two-agent single-machine scheduling problem considering learning effect

Scheduling with multiple agents and learning effect has drawn much attention. In this paper, we investigate the job scheduling problem of two agents competing for the usage of a common single machine with learning effect. The objective is to minimize the total weighted completion time of both agents with the restriction that the makespan of either agent cannot exceed an upper bound. In order to solve this problem we develop several dominance properties and a lower bound based on a branch-and-bound to find the optimal algorithm, and derive genetic algorithm based procedures for finding near-optimal solutions. The performances of the proposed algorithms are evaluated and compared via computational experiments.     

Some scheduling problems with deteriorating jobs and learning effects

Although scheduling with deteriorating jobs and learning effect has been widely investigated, scheduling research has seldom considered the two phenomena simultaneously. However, job deterioration and learning co-exist in many realistic scheduling situations. In this paper, we introduce a new scheduling model in which both job deterioration and learning exist simultaneously. The actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. For the single-machine case, we derive polynomial-time optimal solutions for the problems to minimize makespan and total completion time. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. For the case of an m-machine permutation flowshop, we present polynomial-time optimal solutions for some special cases of the problems to minimize makespan and total completion time.     

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 problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration

Maintenance is important to manufacturing process as it helps improve the efficiency of production. Although different models of joint deterioration and learning effects have been studied extensively in various areas, it has rarely been studied in the context of scheduling with maintenance activities. This paper considers scheduling with jointly the deterioration and learning effects and multi-maintenance activities on a single-machine setting. We assume that the machine may have several maintenance activities to improve its production efficiency during the scheduling horizon, and the duration of each maintenance activity depends on the running time of the machine. The objectives are to determine the optimal maintenance frequencies, the optimal maintenance locations, and the optimal job schedule such that the makespan and the total completion time are minimized, respectively, when the upper bound of the maintenance frequencies on the machine is known in advance. We show that all the problems studied can be solved by polynomial time algorithms.     

Some single-machine scheduling problems with a truncation learning effect

Scheduling with learning effects has received growing attention nowadays. A well-known learning model is called “sum-of processing-times-based learning” in which the actual processing time of a job is a non-increasing 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. Motivated by this observation, we propose a truncation learning model where the actual job processing time is a function which depends not only on the 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. Under the proposed learning model, we show that some single-machine scheduling problems can be solved in polynomial time. In addition, we further provide the worst-case error bounds for the problems to minimize the maximum lateness and total weighted completion time.