Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects

In traditional scheduling problems, the processing time for the given job is assumed to be a constant regardless of whether the job is scheduled earlier or later. However, the phenomenon named “learning effect” has extensively been studied recently, in which job processing times decline as workers gain more experience. This paper discusses a bi-criteria scheduling problem in an m-machine permutation flowshop environment with varied learning effects on different machines. The objective of this paper is to minimize the weighted sum of the total completion time and the makespan. A dominance criterion and a lower bound are proposed to accelerate the branch-and-bound algorithm for deriving the optimal solution. In addition, the near-optimal solutions are derived by adapting two well-known heuristic algorithms. The computational experiments reveal that the proposed branch-and-bound algorithm can effectively deal with problems with up to 16 jobs, and the proposed heuristic algorithms can yield accurate near-optimal solutions.     

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.     

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.     

Several flow shop scheduling problems with truncated position-based learning effect

The concept of truncated position-based learning process plays a key role in production environments. However, it is relatively unexplored in the flow shop setting. In this paper, we consider the flow shop scheduling with truncated position-based learning effect, i.e., the actual processing time of a job is a function of its position and a control parameter in a processing permutation. The objective is to minimize one of the six regular performance criteria, namely, the total completion time, the makespan, the total weighted completion time, the discounted total weighted completion time, the sum of the quadratic job completion times, and the maximum lateness. We present heuristic algorithms and analyze the worst-case bound of these heuristic algorithms. We also provide the computational results to evaluate the performance of the heuristics.     

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.     

Single machine scheduling problems with exponentially time-dependent learning effects

In this paper, we introduce a single-machine scheduling problem with an exponentially time-dependent learning effect. The processing time of a job is assumed to be an exponential function of the total normal processing time of jobs already processed before it. For such a scheduling problem, we first provide the upper bound for the maximum lateness and for the total weighted completion time. Next, we show that problems with the following criteria: makespan, the total completion time, the total weighted completion time, the total earliness/tardiness penalties and the maximum lateness under some agreeable conditions, are polynomially solvable.     

A note on machine scheduling with sum-of-logarithm-processing-time-based and position-based learning effects

Recently, Biskup [2] 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.     

Two-machine flowshop scheduling with truncated learning to minimize the total completion time

Scheduling with learning effects has received a lot of research attention lately. However, the flowshop setting is relatively unexplored. On the other hand, the actual processing time of a job under an uncontrolled learning effect will drop to zero precipitously as the number of jobs increases. This is rather absurd in reality. Motivated by these observations, we consider a two-machine flowshop scheduling problem in which the actual processing time of a job in a schedule is a function of the job’s position in the schedule and a control parameter of the learning function. The objective is to minimize the total completion time. We develop a branch-and-bound and three simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.     

Application of neural networks to heuristic scheduling algorithms

This paper considers the use of artificial neural networks (ANNs) to model six different heuristic algorithms applied to the n job, m machine real flowshop scheduling problem with the objective of minimizing makespan. The objective is to obtain six ANN models to be used for the prediction of the completion times for each job processed on each machine and to introduce the fuzziness of scheduling information into flowshop scheduling. Fuzzy membership functions are generated for completion, job waiting and machine idle times. Different methods are proposed to obtain the fuzzy parameters. To model the functional relation between the input and output variables, multilayered feedforward networks (MFNs) trained with error backpropagation learning rule are used. The trained network is able to apply the learnt relationship to new problems. In this paper, an implementation alternative to the existing heuristic algorithms is provided. Once the network is trained adequately, it can provide an outcome (solution) faster than conventional iterative methods by its generalizing property. The results obtained from the study can be extended to solve the scheduling problems in the area of manufacturing.     

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.     

带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.     

A two-machine flowshop makespan scheduling problem with deteriorating jobs

In traditional scheduling problems, the job processing times are assumed to be known and fixed from the first job to be processed to the last job to be completed. However, in many realistic situations, a job will consume more time than it would have consumed if it had begun earlier. This phenomenon is known as deteriorating jobs. In the science literature, the deteriorating job scheduling problems are relatively unexplored in the flowshop settings. In this paper, we study a two-machine flowshop makespan scheduling problem in which job processing times vary as time passes, i.e. they are assumed as increasing functions of their starting times. First, an exact algorithm is established to solve most of the problems of up to 32 jobs in a reasonable amount of time. Then, three heuristic algorithms are provided to derive the near-optimal solutions. A simulation study is conducted to evaluate the performances of the proposed algorithms. In addition, the impact of the deterioration rate is also investigated.     

基于总加权完成时间的可重入混合流水车间调度问题

研究以最小化总加权完成时间为目标的可重入混合流水车间调度问题(RHFS-TWC),并构建问题的整数规划模型.根据模型的特点,设计基于二维矩阵组的调度解编码方案,结合NEH启发式算法确定工件初始加工顺序,生成高质量初始调度解群.为避免算法陷入早熟及扩大解的搜索空间,给出IGA的遗传参数自适应调整策略,最终形成NEH-IGA融合求解策略.针对不同规模问题分别用传统GA、基于遗传参数自适应调整的IGA、NEH启发式、NEH-IGA算法进行仿真测试,仿真结果表明NEH启发式和遗传参数自适应动态调整策略的引入有效改善了原有GA的求解能力,NEH-IGA算法在求解RHFS-TWC问题方面优势明显.     

An improved heuristic for parallel machine weighted flowtime scheduling with family set-up times

This paper studies the identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted completion time (weighted flowtime). The family set-up time is incurred whenever there is a switch of processing from a job in one family to a job in another family. A heuristic is proposed in this paper for the problem. Computational results show that the proposed heuristic outperforms an existing heuristic, especially for large-sized problems, in terms of both solution quality and computation times. The improvement of solution quality is as high as 4.753% for six-machine problem and 7.822% for nine-machine problem, while the proposed heuristic runs three times faster than the existing one.     

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.     

The three-stage assembly flowshop scheduling problem

We consider the three-stage assembly flowshop scheduling problem with the objective of minimizing the makespan. The three-stage assembly problem generalizes both the serial three machine flowshop problem and the two-stage assembly flowshop scheduling problem and is therefore strongly NP-hard. We analyze the worst-case ratio bound for several heuristics for this problem. We also analyze the worst-case absolute bound for a heuristic based on compact vector summation techniques and we point out that, for a large number of jobs, this heuristic becomes asymptotically optimal.Scope and purposeThe three-stage assembly flowshop scheduling problem models situations which arise frequently in manufacturing when various fabrication operations are performed concurrently and then collected and transported into an assembly area for a final assembly operation. The main criterion for this problem is the minimization of the maximum job completion time (makespan). The objective of this paper is to derive algorithms for minimizing the makespan. In doing so, we also demonstrate the reduction of assembly flowshop problems to their embedded serial flowshop problems.     

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.     

一个求解无等待流水调度问题混合算法

针对以总完工时间最小为目标的无等待流水调度问题提出一个启发式算法和禁忌搜索算法相结合的混合禁忌搜索算法HTS(Hybrid Taboo Search):以启发式算法产生的解作为初始解,通过禁忌搜索提高解的质量.实验结果表明:提出的HTS性能上优于经典的RC1、RC2、PH1(p)和DS算法.     

Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations

This paper addresses a two-agent single-machine scheduling problem with the co-existing sum-of-processing-times-based learning and deteriorating effects. In the proposed model, it is assumed that the actual processing time of a job of the first (second) agent is a decreasing function of the sum-of-processing-times-based learning (or increasing function of the sum-of-processing-times-based deteriorating effect) in a schedule. The aim of this paper is to find an optimal schedule to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. For the proposed model, we develop a branch-and-bound and some ant colony algorithms for an optimal and near-optimal solution, respectively. Besides, the extensive computational experiments are also proposed to test the performance of the algorithms.