Search

Abstract: Recently, machine scheduling problems with deteriorating jobs have received interestingly attention from the scheduling research community. Majority of the research assumed that the actual job processing time is an increasing function of its starting time. However, no job can remain undeteriorated indefinitely in real life situations. This paper considers a single-machine scheduling problem with a truncated linear deteriorating effect and ready times. By the truncated linear deteriorating effect, it means that the actual processing time of a job is a function of its starting time and a control parameter. The objective is to minimize the makespan. A mixed integer programming model and a branch-and-bound algorithm coupled with several dominance properties and two lower bounds are developed to search for the optimal solution. In addition, an ant colony and a Tabu search algorithm where each is refined by the three improvements are also proposed for a near-optimal solution, respectively. A computational experiment is then conducted to evaluate the impacts of the used parameters on the performances of the proposed algorithms. [Copyright &y& Elsevier]

Abstract: This study considers an NP-hard problem of minimizing the total tardiness on a single machine with arbitrary release dates and position-dependent learning effects. A mixed-integer programming (MIP ) model is first formulated to find the optimal solution for small-size problem instances. Some new dominance rules are then presented which provide a sufficient condition for finding local optimality. The branch-and-bound (B& B) strategy incorporating with several dominance properties and a lower bound is proposed to derive the optimal solution for medium- to-large-size problem instances, and four marriage-in-honey-bees optimization algorithms (MBO) are developed to derive near-optimal solutions for the problem. To show the effectiveness of the proposed algorithms, 3600 situations with 20 and 25 jobs, are randomly generated for experiments. [Copyright &y& Elsevier]

Abstract: Scheduling with learning effects has been receiving increasing attention in recent years. However, most researchers assumed that there is a common goal of minimization for all the jobs. In many applications and methodological fields, it is known that multiple agents pursuing different objectives compete for the usage of a common processing resource. In this paper, we studied a single-machine problem with learning effects, where the objective is to minimize the total weighted completion time of jobs from the first agent, given that the number of tardy jobs of the second agent is zero. We proposed a branch-and-bound algorithm and four heuristic algorithms to search for the optimal solution and near-optimal solutions, respectively. [Copyright &y& Elsevier]

Abstract: We consider a scheduling environment with two agents and a linear non-increasing deterioration. By the linear non-increasing deterioration we mean that the actual processing time of a job belonging to the two agents is defined as a non-increasing linear function of its starting time. Two agents compete to perform their respective jobs on a common single machine and each agent has his own criterion to be optimized. The goal is to schedule the jobs such that the combined schedule performs well with respect to the measures of both agents. Three different objective functions are considered for one agent, including the maximum earliness cost, total earliness cost and total weighted earliness cost, while keeping the maximum earliness cost of the other agent below or at a fixed level U. We propose the optimal (nondominated) properties and present the complexity results for the problems addressed here. [Copyright &y& Elsevier]

Abstract: Recently, Biskup classifies the learning effect models in scheduling environments into two types: position-based and sum-of-processing-time-based. In this paper, we study scheduling problem with sum-of-logarithm-processing-time-based and position-based learning effects. We show that the single machine scheduling problems to minimize the makespan and the total completion time can both be solved by the smallest (normal) processing time first (SPT) rule. We also show that the problems to minimize the maximum lateness, the total weighted completion times and the total tardiness have polynomial-time solutions under agreeable WSPT rule and agreeable EDD rule. In addition, we show that m-machine permutation flowshop problems are still polynomially solvable under the proposed learning model. [Copyright &y& Elsevier]

Abstract: Learning effect in scheduling problems has received growing attention since Biskup introduced the position-based model, where the learning curve is expressed as a power function of a job position. Hurley pointed out that the actual processing time of a given job drops to zero precipitously as the number of jobs increases in the standard power model. Moreover, the learning rates show considerable variation within industries or firms. The variation extends not only across firms at a given time, but also within firms over time. For instance, the learning curves usually have an initial downward concavity, and no further improvements are made after some amount of production. Beside the standard power model, learning curve is seldom discussed in scheduling. In this paper, we offer a surprising simple yet realistic learning effect model which has the flexibility to describe different learning curves easily. For instance, the standard power model, the well-known S-shaped and the plateau functions are special cases of the proposed model. We then present the optimal solution for some scheduling problems. [Copyright &y& Elsevier]

Abstract: 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. [ABSTRACT FROM AUTHOR]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: In this note, we point out by a counterexample that the main results in a recent paper by Lee and Lai [W.-C. Lee, P.-J. Lai, Scheduling problems with general effects of deterioration and learning, Inform. Sci. 181 (2011) 1164–1170] are incorrect, and provide a sufficient condition for them being true. [Copyright &y& Elsevier]