Some single-machine and flowshop scheduling problems with a non-linear deterioration function

The deteriorating job scheduling problems have received increasing attention recently. However, most researchers assume that the actual job processing time is a linear function of its starting time. In fact, in some situations, the deterioration rate might increase or decrease as time passes. For example, the temperature of the ingot in the rolling machine might drop at a slower pace as the surface cools down. Thus, the drop of the ingot temperature might have a decreasing rate. On the other hand, the time to control a fire might go dramatically as time passes, and the time to cease a fire might have an increasing rate. In this paper, we propose a new deteriorating model where the deterioration rate might be increasing or decreasing as time passes. Under the proposed model, we provide the optimal solutions for some single-machine problems and some flowshop problems.     

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.     

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.     

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.     

Scheduling problems with general effects of deterioration and learning

Scheduling with deteriorating jobs or learning effects has been widely studied recently. There are situations where both the deterioration and learning effects might exist at the same time. However, the research with the consideration of both the effects is relatively limited. Furthermore, the forms of the effects are specific functions in the literature. In this paper, we introduce a general scheduling model in the sense that the form of the function is unspecified. Under the proposed model, the actual job processing time is a general function on the processing times of the jobs already processed and its scheduled position. The optimal solutions for some single-machine problems are provided.     

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.     

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.     

Notes on “some single-machine scheduling problems with general position-dependent and time-dependent learning effects”

This paper provides a continuation of the idea presented by Yin et al. [Yin et al., Some scheduling problems with general position-dependent and time-dependent learning effects, Inform. Sci. 179 (2009) 2416-2425]. For each of the following three objectives, total weighted completion time, maximum lateness and discounted total weighted completion time, this paper presents an approximation algorithm which is based on the optimal algorithm for the corresponding single-machine scheduling problem and analyzes its worst-case bound. It shows that the single-machine scheduling problems under the proposed model can be solved in polynomial time if the objective is to minimize the total lateness or minimize the sum of earliness penalties. It also shows that the problems of minimizing the total tardiness, discounted total weighted completion time and total weighted earliness penalty are polynomially solvable under some agreeable conditions on the problem parameters.     

Single-machine group scheduling problems under the effects of deterioration and learning

This paper investigates single-machine group scheduling problems with simultaneous considerations of deteriorating and learning effects to minimize the makespan and the total completion time of all jobs. The group setup time is assumed to follow a simple linear time-dependent deteriorating model. Two models of learning for the job processing time are examined in this study. We provided polynomial time solutions for the makespan minimization problems. We also showed that the total completion time minimization problems remain polynomially solvable under agreeable 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.     

Stochastic scheduling problems with general position-based learning effects and stochastic breakdowns

The focus of this study is to analyze position-based learning effects in single-machine stochastic scheduling problems. The optimal permutation policies for the stochastic scheduling problems with and without machine breakdowns are examined, where the performance measures are the expectation and variance of the makespan, the expected total completion time, the expected total weighted completion time, the expected weighted sum of the discounted completion times, the maximum lateness and the maximum tardiness.     

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.     

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.     

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.     

Solving a single-machine scheduling problem with maintenance,job deterioration and learning effect by simulated annealing

This paper presents a new nonlinear multi-objective mathematical model for a single-machine scheduling problem with three objectives: (1) minimizing the sum of the weighted jobs completion, (2) minimizing the sum of the weighted delay times, and (3) maximizing the sum of the job values in makespan. In addition, a number of constraints are incorporated in this presented model, such as repairing and maintenance periods, deterioration of jobs, and learning effect of the work process. Since this type of scheduling problem belongs to a class of NP-hard ones, its solution by common software packages is almost impossible, or at best very time consuming. Thus, a meta-heuristic algorithm based on simulated annealing (SA) is proposed to solve such a hard problem. At a final stage, the related results obtained by the proposed SA are compared with those results reported by the Lingo 8 software in order to demonstrate the efficiency and capability of our proposed SA algorithm.     

A single-machine scheduling problem with learning effects in intermittent batch production

This paper studies a 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. The phenomena exist in many realistic production systems. The objective is to minimize the makespan. We show that the problems with the models of no transmission and partial transmission of learning from batch to batch are polynomially solvable. We also provide two polynomial time algorithms for two special cases in the problem with the total transmission model.     

A bi-criterion single-machine scheduling problem with learning considerations

Conventionally, job processing times are assumed to be constant from the first job to be processed until the last job to be completed. However, recent empirical studies in several industries have verified that unit costs decline as firms produce more of a product and gain knowledge or experience. This phenomenon is known as the learning effect. This paper focuses on a bi-criterion single-machine scheduling problem with a learning effect. The objective is to find a sequence that minimizes a linear combination of the total completion time and the maximum tardiness. A branch-and-bound and a heuristic algorithm are proposed to search for optimal and near-optimal solutions, respectively. Computational results are also provided for the problem.Received: 21 April 2003, Accepted: 9 October 2003, Published online: 16 January 2004     

Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects

In this paper, we study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup time of each job is past-sequence-dependent. The objectives are to minimize the total absolute deviation of job completion times and the total load on all machines, respectively. We show that the proposed problem is polynomially solvable. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.     

A tabu method for a two-agent single-machine scheduling with deterioration jobs

In recent 10 years, the multi-agent idea applied in scheduling issues has received continuing attention. However, the study of the multi-agent scheduling with deteriorating jobs is relatively limited. In light of this, this paper deliberates upon a two-agent single-machine scheduling problem with deteriorating jobs. Taking the proposed model, the actual processing time of a job from both the first agent and the second agent is modeled as a linearly increasing function of its starting time. The goal of this paper is to minimize the total weighted number of tardy jobs of the first agent subject to the condition that the maximum lateness of the second agent is allowed to have an upper bound. The complexity of the model concerned in the paper is claimed as an NP-hard one. Following that, several dominance rules and a lower bound are proposed to be applied in a branch-and-bound algorithm for the optimal solution, and a tabu algorithm is applied to find near-optimal solutions for the problem. The simulation results obtained from all the proposed algorithms are also reported.     

A single-machine bi-criterion learning scheduling problem with release times

The learning effect in scheduling has received considerable attention recently. However, most researchers consider a single criterion with the assumption that jobs are all ready to be processed. The research of bi-criterion problems with learning effect is relatively limited. This paper studies a single-machine learning effect scheduling problem with release times where the objective is to minimize the sum of makespan and total completion time. First, we develop a branch-and-bound algorithm incorporating with several dominance properties and a lower bound to derive the optimal solution. Secondly, we propose a genetic algorithm to obtain near-optimal solutions. Finally, a computational experiment is conducted to evaluate the performance of the branch-and-bound and the genetic algorithms.