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.     

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 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.     

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.     

Scheduling with due date assignment under special conditions on job processing

We review the results on scheduling with due date assignment under such conditions on job processing as given precedence constraints, maintenance activity or various scenarios of processing time changing. The due date assignment and scheduling problems arise in production planning when the management is faced with setting realistic due dates for a number of jobs. Most research on scheduling with due date assignment is focused on optimal sequencing of independent jobs. However, it is often found in practice that some products are manufactured in a certain order implied, for example, by technological, marketing or assembly requirements and this can be modeled by imposing precedence constraints on the set of jobs. In classical deterministic scheduling models, the processing conditions, including job processing times, are usually viewed as given constants. In many real-life situations, however, the processing conditions may vary over time, thereby affecting actual durations of jobs. In the models with controllable processing times, the scheduler can speed up job execution times by allocating some additional resources to the jobs. In the models with deterioration or learning, the actual processing time can depend either on the position or on the start time of a job in the schedule. In scheduling with deterioration, the later a job starts, the longer it takes to process, while in scheduling with learning, the actual processing time of a job gets shorter, provided that the job is scheduled later. We consider also scheduling models with optional maintenance activity. In manufacturing processing, production scheduling with preventive maintenance planning is one of the most significant methods in preventing the machinery from failure or wear.     

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.     

Some single-machine scheduling problems with a truncation learning effect

Scheduling with learning effects has received growing attention nowadays. A well-known learning model is called “sum-of processing-times-based learning” in which the actual processing time of a job is a non-increasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Motivated by this observation, we propose a truncation learning model where the actual job processing time is a function which depends not only on the processing times of the jobs already processed but also on a control parameter. The use of the truncated function is to model the phenomenon that the learning of a human activity is limited. Under the proposed learning model, we show that some single-machine scheduling problems can be solved in polynomial time. In addition, we further provide the worst-case error bounds for the problems to minimize the maximum lateness and total weighted completion time.     

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.     

Single-machine scheduling with a nonlinear deterioration function

In deteriorating job scheduling problems, most of the researchers assume that the actual job processing time is a function of its starting time. In this paper, we propose a new deterioration model in which the actual job processing time is a general function of the normal processing time of jobs already processed and its scheduled position at the same time. We show that some single-machine scheduling problems remain polynomially solvable.     

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

This paper studies a single machine scheduling problem with setup times and learning considerations. The setup times are proportional to the length of the already scheduled jobs. That is, the setup times are past-sequence-dependent. It is assumed that the learning process reflects a decrease in the process time as a function of the number of repetitions, i.e., as a function of the job position in the sequence. The following objectives are considered: the makespan, the total completion time, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalty. Polynomial time algorithms are proposed to optimally solve the above objective functions.     

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.     

Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

A note on single-machine scheduling with general learning effect and past-sequence-dependent setup time

In this paper, we study a scheduling model with the consideration of both the learning effect and the setup time. Under the proposed model, the learning effect is a general function of the processing time of jobs already processed and its scheduled position, and the setup time is past-sequence-dependent. We then derive the optimal sequences for two single-machine problems, which are the makespan and the total completion time. Moreover, we showed that the weighted completion time, the maximum lateness, the maximum tardiness, and the total tardiness problems remain polynomially solvable under agreeable conditions.     

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.     

On-line scheduling of two parallel machines with a single server

In this paper, we consider the on-line scheduling of two parallel identical machines sharing a single server with the objective of minimizing the latest completion time of all jobs. Each job has to be setup by the server before being processed on one of the machines. Three special cases: equal length jobs, equal processing times and regular equal setup times are considered and the asymptotic competitive ratios of list scheduling are determined. Also, a lower bound for the equal length job case is given, and two heuristics with tight asymptotic competitive ratios for the other two cases are proposed.     

Single machine common flow allowance scheduling with a rate-modifying activity

In this paper we consider single machine SLK due date assignment scheduling problem with a rate-modifying activity. In this model, the machine has a rate-modifying activity that can change the processing rate of machine under consideration. Hence the actual processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. We need to make a decision on when to schedule the rate-modifying activity, the optimal common flow allowance and the sequence of jobs to minimize total earliness, tardiness and common flow allowance cost. We introduce an efficient (polynomial time) solution for this problem.     

Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

We study a supply chain scheduling problem in which n jobs have to be scheduled on a single machine and delivered to m customers in batches. Each job has a due date, a processing time and a lateness penalty (weight). To save batch-delivery costs, several jobs for the same customer can be delivered together in a batch, including late jobs. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time has to be added before processing the first job in each batch. The objective is to find a schedule which minimizes the sum of the weighted number of late jobs and the delivery costs. We present a pseudo-polynomial algorithm for a restricted case, where late jobs are delivered separately, and show that it becomes polynomial for the special cases when jobs have equal weights and equal delivery costs or equal processing times and equal setup times. We convert the algorithm into an FPTAS and prove that the solution produced by it is near-optimal for the original general problem by performing a parametric analysis of its performance ratio.     

Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects

In this paper, we study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup time of each job is past-sequence-dependent. The objectives are to minimize the total absolute deviation of job completion times and the total load on all machines, respectively. We show that the proposed problem is polynomially solvable. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.