在成组技术下带恶化和学习效应的单机排序问题

本文研究了带依靠时间的恶化效应和依靠位置的学习效应的成组排序问题。模型中,组安装时间是开始安装时间的线性函数,工件的加工时间带恶化和学习效应,目标函数分别为最小化时间表长问题和最小化总完工时间问题。基于对问题的分析,给出了多项式算法。     

Trapezoidal type inequalities for n-time differentiable functions

In this paper we consider the flow shop scheduling problems with the effects of learning and deterioration. In this model the processing times of a job is defined as a function of its starting time and position in a sequence. The scheduling objective functions are makespan and total completion time. We prove that even with the introduction of learning effect and deteriorating jobs to job processing times, some special flow shop scheduling problems remain polynomially solvable.     

带恶化和综合学习效应的成组排序问题研究

本文研究了成组技术下带恶化和综合学习效应的排序问题,工件的加工时间带综合学习效应。对最小化时间表长问题,我们给出了多项式算法,并且证明了带一致关系的最小化总完工时间问题也是多项式可解的。     

Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine

We consider scheduling problems with learning/deterioration effects and time-dependent processing times on a single machine, with or without due date assignment considerations. By reducing them to a special assignment problem on product matrices, we solve all these problems in near-linear time. This improves the time complexity of previous algorithms for some scheduling problems and establishes the fast polynomial solvability for several other problems.     

Single-machine scheduling with effects of exponential learning and general deterioration

The purpose of this study is to explore the single-machine scheduling with the effects of exponential learning and general deterioration. By the effects of exponential learning and general deterioration, we meant that job processing time is decided by the functions of their starting time and positions in the sequence. Results showed that with the introduction of learning effect and deteriorating jobs to job processing time, single-machine makespan, and sum of completion time (square) minimization problems remained polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion time and the maximum lateness, this paper proved that the weighted smallest basic processing time first (WSPT) rule and the earliest due date first (EDD) rule constructed the optimal sequence under some special cases, respectively.     

Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning

This paper investigates a single machine serial-batching scheduling problem considering release times, setup time, and group scheduling, with the combined effects of deterioration and truncated job-dependent learning. The objective of the studied problem is to minimize the makespan. Firstly, we analyze the special case where all groups have the same arrival time, and propose the optimal structural properties on jobs sequencing, jobs batching, batches sequencing, and groups sequencing. Next, the corresponding batching rule and algorithm are developed. Based on these properties and the scheduling algorithm, we develop a hybrid VNS–ASHLO algorithm incorporating variable neighborhood search (VNS) and adaptive simplified human learning optimization (ASHLO) algorithms to solve the general case of the studied problem. Computational experiments on randomly generated instances are conducted to compare the proposed VNS–ASHLO with the algorithms of VNS, ASHLO, Simulated Annealing (SA), and Particle Swarm Optimization (PSO). The results based on instances of different scales show the effectiveness and efficiency of the proposed algorithm.     

Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning

In this paper we consider the single-machine setup times scheduling with general effects of deterioration and learning. By the general effects of deterioration and learning, we mean that the actual job processing time is a general function of the processing times of the jobs already processed and its scheduled position. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We show that the problems to minimize the makespan, the sum of the δ$\delta$th (δ>0$\delta >0$) power of job completion times, the total lateness are polynomially solvable. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness (tardiness) minimization problem, the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Scheduling deteriorating jobs with a learning effect on unrelated parallel machines

In this study we consider unrelated parallel machines scheduling problems with learning effect and deteriorating jobs, in which the actual processing time of a job is a function of joint time-dependent deterioration and position-dependent learning. The objective is to determine the jobs assigned to corresponding each machine and the corresponding optimal schedule to minimize a cost function containing total completion (waiting) time, total absolute differences in completion (waiting) times and total machine load. If the number of machines is a given constant, we show that the problems can be solved in polynomial time under the time-dependent deterioration and position-dependent learning model.     

Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with a general position-dependent learning effects. By the general position-dependent learning effects, we mean that the actual processing time of a job is defined by a general non-increasing function of its scheduled position. The objective is to minimize one of the five regular performance criteria, namely, the total completion time, the makespan, the total weighted completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems. We also analyze the worst-case bound of our heuristic algorithms.     

Scheduling jobs with a general learning effect model

The paper deals with machine scheduling problems with a general learning effect. By the general learning effect, we mean that the actual processing time of a job is not only a non-increasing function of the total weighted normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence, where the weight is a position-dependent weight. We show that even with the introduction of a general learning effect to job processing times, some single machine scheduling problems are still polynomially solvable under the proposed model. We also show that some special cases of the flow shop scheduling problems can be solved in polynomial time.     

Some single-machine scheduling with both learning and deterioration effects

In this paper we consider the single-machine scheduling problems with both learning and deterioration effects. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single-machine makespan minimization problem and the sum of the θth power of job completion times minimization problem remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively.     

Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine

Group technology is important to manufacturing as it helps increase the efficiency of production and decrease the requirement of facilities. In this paper we investigate group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine setting. The learning phenomenon is implemented to model the setup time of groups. Three models of deteriorating for the job processing time within a group are examined. We show that all the problems studied are polynomially solvable with or without the presence of certain conditions where the objective is to find an optimal schedule for minimizing the makespan. We also investigate the minimization of the total completion time. We proved that one of the deterioration models examined in this study can also be solved in a polynomial time algorithm under certain conditions.     

Single machine scheduling with a time-dependent learning effect and deteriorating jobs

The paper deals with the single machine scheduling problems with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the processing time of a job is defined by function of its starting time and total normal processing time of jobs in front of it in the sequence. It is shown that even with the introduction of a time-dependent learning effect and deteriorating jobs to job processing times, the single machine makespan minimization problem remain polynomially solvable. But for the total completion time minimization problem, the classical shortest processing time first rule or largest processing time first rule cannot give an optimal solution.     

Some scheduling problems with time-dependent learning effect and deteriorating jobs

Although machine scheduling problems with learning and deteriorating effects consideration have received increasing attention in the recent years, most studies have seldom considered the two phenomena simultaneously. However, learning and deteriorating effects might co-exist in many realistic scheduling situations. Thus, in this article, a model which takes the effects of time-dependent learning and deterioration simultaneously is proposed and applied into some scheduling problems. Under the proposed model, the processing time of a job is determined by a function of its corresponding starting time and positional sequence in each machine. We show that some single machine and flowshop scheduling problems are polynomially solvable with the certain performance measures such as makespan, total completion time, and weighted completion time.     

Several single-machine scheduling problems with general learning effects

In this paper we consider several single-machine scheduling problems with general learning effects. By general learning effects, we mean that the processing time of a job depends not only on its scheduled position, but also on the total normal processing time of the jobs already processed. We show that the scheduling problems of minimization of the makespan, the total completion time and the sum of the θ  th (θ?0$\theta ?0$) power of job completion times can be solved in polynomial time under the proposed models. We also prove that some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time.     

Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions

Scheduling with learning effects has received growing attention nowadays. A well-known learning model is called ‘position-based learning’ in which the actual processing time of a job is a non-increasing function of its position to be processed. However, the actual processing time of a given job drops to zero precipitously as the number of jobs increases. Motivated by this observation, we propose two truncated learning models in single-machine scheduling problems and two-machine flowshop scheduling problems with ordered job processing times, respectively, where the actual processing time of a job is a function of its position and a control parameter. Under the proposed learning models, we show that some scheduling problems can be solved in polynomial time. In addition, we further analyse the worst-case error bounds for the problems to minimize the total weighted completion time, discounted total weighted completion time and maximum lateness.     

Research on permutation flow shop scheduling problems with general position-dependent learning effects

Machine learning exists in many realistic scheduling situations. This study focuses on permutation flow shop scheduling problems, where the actual processing time of a job is defined by a general non-increasing function of its scheduled position, i.e., general position-dependent learning effects. The objective functions are to minimize the total completion time, the makespan, the total weighted completion time, and the total weighted discounted completion time, respectively. To solve these problems, we present approximation algorithms based on the optimal permutations for the corresponding single machine scheduling problems and analyze their worst-case error bound.     

Note on “A note on single-machine group scheduling problems with position-based learning effect”

In a recent paper, Lee and Wu [W.-C. Lee, C.-C. Wu, A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model. 33 (2009) 2159–2163] proposed a new group scheduling learning model where the learning effect not only depends on the job position, but also depends on the group position. They investigate the makespan and the total completion time minimization problems on a single-machine. As for the total completion time minimization problem, they assumed that the numbers of jobs in each group are the same and the group normal setup and the job normal processing times are agreeable. Under the assumption conditions, they showed that the total completion time minimization problem can be optimally solved in polynomial time solution. However, the assumption conditions for the total completion time minimization problem do not reflect actual practice in many manufacturing processes. Hence, in this note, we propose other agreeable conditions and show that the total completion time minimization problem remains polynomially solvable under the agreeable conditions.     

The single machine total weighted completion time scheduling problem with the sum-of-processing time based models: Strongly NP-hard

Although the single machine scheduling problem to minimize the total weighted completion times with the sum-of-processing time based learning or aging effects have been known for a decade, it is still an open question whether these problems are strongly NP-hard. We resolve this issue and prove them to be strongly NP-hard with the learning effect as well as with the aging effect. Furthermore, we construct an exact parallel branch and bound algorithm for the problem with general sum-of-processing time based models, which can solve optimally moderate problem instances in reasonable time.     

Scheduling problems with position dependent job processing times: computational complexity results

In this paper, we analyse single machine scheduling problems with learning and aging effects to minimize one of the following objectives: the makespan with release dates, the maximum lateness and the number of late jobs. The phenomena of learning and aging are modeled by job processing times described by non-increasing (learning) or non-decreasing (aging) functions dependent on the number of previously processed jobs, i.e., a job position in a sequence. We prove that the considered problems are strongly NP-hard even if job processing times are described by simple linear functions dependent on a number of processed jobs. Additionally, we show a property of equivalence between problems with learning and aging models. We also prove that if the function describing decrease/increase of a job processing time is the same for each job then the problems with the considered objectives are polynomially solvable even if the function is arbitrary. Therefore, we determine the boundary between polynomially solvable and strongly NP-hard cases.