Single-machine scheduling problems with actual time-dependent and job-dependent learning effect

In this study, we introduce an actual time-dependent and job-dependent learning effect into single-machine scheduling problems. We show that the complexity results of the makespan minimization problem and the sum of weighted completion time minimization problem are all NP-hard. The complexity result of the maximum lateness minimization problem is NP-hard in the strong sense. We also provide three special cases which can be solved by polynomial time algorithms.     

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.     

Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect

In this paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Single machine scheduling with truncated job-dependent learning effect

In this paper we consider the single machine scheduling problem with truncated job-dependent learning effect. By the truncated job-dependent learning effect, we mean that the actual job processing time is a function which depends not only on the job-dependent learning effect (i.e., the learning in the production process of some jobs to be faster than that of others) but also on a control parameter. The objectives are to minimize the makespan, the total completion time, the total absolute deviation of completion time, the earliness, tardiness and common (slack) due-date penalty, respectively. Several polynomial time algorithms are proposed to optimally solve the problems with the above objective functions.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the 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 setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Single-machine scheduling with a sum-of-actual-processing-time-based learning effect

In this paper we consider the single-machine scheduling problems with a sum-of-actual-processing-time-based learning effect. By the sum-of-actual-processing-time-based learning effect, we mean that the processing time of a job is defined by a function of the sum of the actual processing time of the already processed jobs. We show that even with the introduction of the sum-of-actual-processing-time-based learning effect to job processing times, the makespan minimization problem, the total completion time minimization problem, the total completion time square minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem remain polynomially solvable, respectively.     

Single-machine scheduling with a general sum-of-actual-processing-times-based and job-position-based learning effect

In this paper, we bring into the scheduling field a general learning effect model where the actual processing time of a job is not only a general function of the total actual processing times of the jobs already processed, but also a general function of the job’s scheduled position. We show that the makespan minimization problem and the sum of the kth power of completion times minimization problem can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

基于加工时间之和学习效应下的单机成组排序问题

研究具有加工时间之和学习效应下的一个新型成组排序问题,工件的学习效应是之前工件加工时间之和的函数,组学习效应是成组加工所在的位置的函数. 考虑最大完工时间和总完工时间两个问题,证明了这两个问题都是多项式时间可解的,并提出了相应的多项式时间算法.     

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.     

Scheduling jobs with position-dependent processing times

The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.     

Scheduling in bicriteria single machine systems with past-sequence-dependent setup times and learning effects

Scheduling with setup times and learning plays a crucial role in today's manufacturing and service environments where scheduling decisions are made with respect to multiple performance criteria rather than a single criterion. In this paper, we address a bicriteria single machine scheduling problem with job-dependent past-sequence-dependent setup times and job-dependent position-based learning effects. The setup time and actual processing time of a job are respectively unique functions of the actual processing times of the already processed jobs and the position of the job in a schedule. The objective is to derive the schedule that minimizes a linear composite function of a pair of performance criteria consisting of the makespan, the total completion time, the total lateness, the total absolute differences in completion times, and the sum of earliness, tardiness, and common due date penalty. We show that the resulting problems cannot be solved in polynomial time; thus, branch-and-bound (B&B) methods are proposed to obtain the optimal schedules. Our computational results demonstrate that the B&B can solve instances of various size problems with attractive times.     

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

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

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.     

带有退化效应和序列相关运输时间的排序问题

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.     

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.     

Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect

This paper considers identical parallel-machine scheduling problem with past-sequence-dependent (psd) delivery times and learning effect. In electronic manufacturing industry, an electronic component may be exposed to certain electromagnetic field and requires an extra time for eliminating adverse effect after the main processing. The extra time is modeled as past-sequence-dependent delivery time in the literature, which is proportional to the waiting time in the system. It is also observed that the learning process reflects a decrease in the processing time as a function of the number of repetitions, i.e., as a function of the job position in the sequence. In practice, one often has to deal with the scheduling problems with psd delivery times and learning effect. Identical parallel-machine setting is considered because the occurrence of resources in parallel is common in the real world. In this paper, three objectives are the minimization of the total absolute deviation of job completion times, the total load on all machines and the total completion time. We develop polynomial algorithms to optimally solve these problems.     

Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects

In this paper we consider the single machine past-sequence-dependent (p-s-d) setup times scheduling problems with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects, we mean that 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. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem, maximum tardiness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions.     

Single-machine scheduling with both deterioration and learning effects

This paper considers a single-machine scheduling problem with both deterioration and learning effects. The objectives are to respectively minimize the makespan, the total completion times, the sum of weighted completion times, the sum of the kth power of the job completion times, the maximum lateness, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalties. Several polynomial time algorithms are proposed to optimally solve the problem with the above objectives.     

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.     

Some single-machine scheduling with sum-of-processing-time-based and job-position-based processing times

The single-machine scheduling problems with position and sum-of-processing-time based processing times are considered. The actual processing time of a job is defined by function of its scheduled position and total normal processing time of jobs in front of it in the sequence. We provide optimal solutions in polynomial time for some special cases of the makespan minimization and the total completion time minimization. We also show that an optimal schedule to be a V-shaped schedule in terms of the normal processing times of jobs for the total completion time minimization problem and the makespan minimization problem.