A note on scheduling problems with learning effect and deteriorating jobs

In this note, we consider the machine scheduling problems with the effects of deterioration and learning. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The scheduling objectives are makespan (weighted) sum of completion times and maximum lateness. It is shown that even with the introduction of deterioration and learning effect to job processing times, several single machine problems and several flow shop problems remain polynomially solvable, respectively.     

One-machine scheduling problems with deteriorating jobs and position-dependent learning effects under group technology considerations

In this paper, we introduce a group scheduling model with general deteriorating jobs and learning effects in which deteriorating jobs and learning effects are both considered simultaneously. This means 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. In our model, the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent learning effects and time-dependent deterioration. The objective of scheduling problems is to minimise the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model.     

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.     

具有线性恶化加工时间的调度问题

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性 函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费 用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用 Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则 Flowshop问题可以转化为单机问题.     

Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect

In this paper, we investigate a time-dependent learning effect in a flowshop scheduling problem. We assume that the time-dependent learning effect of a job was a function of the total normal processing time of jobs scheduled before the job. The following objective functions are explored: the makespan, the total flowtime, the sum of weighted completion times, the sum of the kth power of completion times, and the maximum lateness. Some heuristic algorithms with worst-case analysis for the objective functions are given. Moreover, a polynomial algorithm is proposed for the special case with identical processing time on each machine and that with an increasing series of dominating machines, respectively. Finally, the computational results to evaluate the performance of the heuristics 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.     

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.     

Makespan minimization flowshop with position dependent job processing times—computational complexity and solution algorithms

This paper considers flowshop scheduling problems where job processing times are described by position dependent functions, i.e., dependent on the number of processed jobs, that model learning or aging effects. We prove that the two-machine flowshop problem to minimize the maximum completion time (makespan) is NP-hard if job processing times are described by non-decreasing position dependent functions (aging effect) on at least one machine and strongly NP-hard if job processing times are varying on both machines. Furthermore, we construct fast NEH, tabu search with a fast neighborhood search and simulated annealing algorithms that solve the problem with processing times described by arbitrary position dependent functions that model both learning and aging effects. The efficiency of the proposed methods is numerically analyzed.     

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.     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.     

Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times

The single-machine scheduling problem with truncated sum-of-processing-times-based learning effect and past-sequence-dependent job delivery times is considered. Each job’s delivery time depends on its waiting time of processing. For some regular objective functions, it is proved that the problems can be solved by the smallest processing time first rule. For some special cases of the total weighted completion time and the maximum lateness objective functions, the thesis shows that the problems can be solved in polynomial time.     

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 total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

Two-machine flow shop problem with effects of deterioration and learning

In this paper we consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions.     

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.     

The solution algorithms for the multiprocessor scheduling with workspan criterion

In this paper, we consider multiprocessor scheduling problems, where each job (task) must be executed simultaneously by the specified number of processors, but the indices of the processors allotted to each job do not have to be contiguous (i.e., jobs can be fragmentable). Unlike other research in this domain, we analyse the problem under the workspan criterion, which is defined as the product of the maximum job completion time (makespan) and the number of used processors. Moreover, the job processing times can be described by non-increasing or non-decreasing functions dependent on the start times of jobs that model improvement (learning) or degradation (deteriorating), respectively. To solve the problems, we construct some polynomial time algorithms and analyse numerically their efficiency.     

The common due-date early/tardy scheduling problem on a parallelmachine under the effects of time-dependent learning and linear and nonlinear deterioration

This paper considers earliness/tardiness (ET) scheduling problem on a parallel machine environment with common due-date under the effects of time-dependent learning and linear and nonlinear deterioration. In this paper, the effects of learning and deterioration are considered simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. This study shows that optimal solution for ET scheduling problem under effects of learning and deterioration is V-shape schedule under certain agreeable conditions. Furthermore, we present a mathematical model for the problem under study and an algorithm for solving large test problems. The algorithm can solve problems of 1000 jobs and four machines within 3 s on average.     

Scheduling jobs with mixed processing times,arbitrary precedence constraints and maximum cost criterion

We consider single-machine scheduling problems with variable job processing times, arbitrary precedence constraints and maximum cost criterion. We show how to solve the problems in polynomial time in the cases when job processing times are described by functions of the same type or when they are mixed, i.e. some of them are fixed, while the other ones are variable and take into account the effects of learning, ageing or job deterioration.     

Parallel machine scheduling problem to minimize the earliness/tardiness costs with learning effect and deteriorating jobs

The focus of this work is to analyze parallel machine earliness/tardiness (ET) scheduling problem with simultaneous effects of learning and linear deterioration, sequence-dependent setups, and a common due-date for all jobs. By the effects of learning and linear deterioration, we mean that the processing time of a job is defined by an increasing function of its starting time and a decreasing function of the position in the sequence. We develop a mixed integer programming formulation for the problem and show that the optimal sequence is V-shaped: all jobs scheduled before the shortest jobs and all jobs scheduled after the shortest job are in a non-increasing and non-decreasing order of processing times, respectively. The developed model allows sequence-dependent setups and sequence-dependent early/tardy penalties. The illustrative example with 11 jobs for 2 machines and 3 machines shows that the model can easily provide the optimal solution, which is V-shaped, for problem.