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.     

Scheduling problems with deteriorating jobs and learning effects including proportional setup times

Recently, interest in scheduling with deteriorating jobs and learning effects has kept growing. However, research in this area has seldom considered setup times. We introduce a new scheduling model in which job deterioration and learning, and setup times are considered simultaneously. In the proposed model, the actual processing time of a job is defined as a function of the setup and processing times of the jobs already processed and the job’s own scheduled position in a sequence. In addition, the setup times are assumed to be proportional to the actual processing times of the already scheduled jobs. We derive polynomial-time optimal solutions for some single-machine problems with or without the presence of certain conditions.     

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.     

Single-machine scheduling with learning effect and deteriorating jobs

In this paper we consider the single-machine scheduling problems with the effects of learning and deterioration. 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 and sum of completion times (square) minimization problems 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.     

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.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist 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. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.     

Single-machine scheduling with deteriorating jobs under a series–parallel graph constraint

This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series–parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.     

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.     

Three scheduling problems with deteriorating jobs to minimize the total completion time

In this paper, three scheduling problems with deteriorating jobs to minimize the total completion time on a single machine are investigated. By a deteriorating job, we mean that the processing time of the job is a function of its execution start time. The three problems correspond to three different decreasing linear functions, whose increasing counterparts have been studied in the literature. Some basic properties of the three problems are proved. Based on these properties, two of the problems are solved in O(nlogn) time, where n is the number of jobs. A pseudopolynomial time algorithm is constructed to solve the third problem using dynamic programming. Finally, a comparison between the problems with job processing times being decreasing and increasing linear functions of their start times is presented, which shows that the decreasing and increasing linear models of job processing times seem to be closely related to each other.     

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.     

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.     

Parallel machine match-up scheduling with manufacturing cost considerations

Many scheduling problems in practice involve rescheduling of disrupted schedules. In this study, we show that in contrast to fixed processing times, if we have the flexibility to control the processing times of the jobs, we can generate alternative reactive schedules considering the manufacturing cost implications in response to disruptions. We consider a non-identical parallel machining environment where processing times of the jobs are compressible at a certain manufacturing cost, which is a convex function of the compression on the processing time. In rescheduling it is highly desirable to catch up the original schedule as soon as possible by reassigning the jobs to the machines and compressing their processing times. On the other hand, one must also keep the manufacturing cost due to compression of the jobs low. Thus, one is faced with a tradeoff between match-up time and manufacturing cost criteria. We introduce alternative match-up scheduling problems for finding schedules on the efficient frontier of this time/cost tradeoff. We employ the recent advances in conic mixed-integer programming to model these problems effectively. We further provide a fast heuristic algorithm driven by dual prices of convex subproblems for generating approximate efficient schedules.     

Single machine scheduling with precedence constraints and positionally dependent processing times

In many real-life situations the processing conditions in scheduling models cannot be viewed as given constants since they vary over time thereby affecting actual durations of jobs. We consider single machine scheduling problems of minimizing the makespan in which the processing time of a job depends on its position (with either cumulative deterioration or exponential learning). It is often found in practice that some products are manufactured in a certain order implied, for example, by technological, marketing or assembly requirements. This can be modeled by imposing precedence constraints on the set of jobs. We consider scheduling models with positional deterioration or learning under precedence constraints that are built up iteratively from the prime partially ordered sets of a bounded width (this class of precedence constraints includes, in particular, series-parallel precedence constraints). We show that objective functions of the considered problems satisfy the job module property and possess the recursion property. As a result, the problems under consideration are solvable in polynomial 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.     

A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity

This note considers a single machine scheduling and due-window assignment problem, in which the processing time of a job is a linear function of its starting time and the job-independent deterioration rates are identical for all jobs. We allow an option for performing a rate-modifying activity for changing the normal processing times of the jobs following this activity. The objective is to schedule the jobs, the due-window and the rate-modifying activity so as to minimize the sum of earliness, tardiness and due-window starting time and due-window size costs. We introduce a polynomial solution for the problem.     

Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration

This paper considers a parallel machine earliness/tardiness (ET) scheduling problem with different penalties under the effects of position based learning and linear and nonlinear deterioration. The problem has common due-date for all jobs, and effects of learning and deterioration are considered simultaneously. By the effects of learning we mean that the job processing time decreases along the sequence of partly similar jobs, and by the effects of deterioration we mean slowing performance or time increases along the sequence of jobs. 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 design a mathematical model for the problem under study and algorithm and lower bound procedure to solve larger test problems. The algorithm can solve problems of 1000 jobs and four machines within 3 s on average. The performance of the algorithm is evaluated using results of the mathematical model.     

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.     

Two due date assignment problems with position-dependent processing time on a single-machine

The focus of this study is to analyze single-machine scheduling and due date assignment problems with position-dependent processing time. Two generally positional deterioration models and two frequent due date assignment methods are investigated. The objective functions include the cost of changing the due dates, the total cost of positional weight earliness, and the total cost of the discarded jobs that cannot be completed by their due dates. We conclude that the problems are polynomial time solvable. Significantly enough, after assessing the special case of each problem, this research found out that they can be optimally solved by lower order algorithms.