Deteriorating jobs and learning effects on a single-machine scheduling with past-sequence-dependent setup times

In this paper, we consider the single-machine setup times scheduling with the effects of learning and deterioration. By the effects of learning and deterioration, we mean that 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. 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 total completion time, and the sum of the $\mathit{\delta}$ th ( ${\mathit{\delta}} \geq 0$ ) power of job completion times are polynomially solvable. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem, and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions.     

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

The paper deals with some single-machine scheduling problems with setup time considerations where the processing time of a job is given as a function of its starting times and position in a sequence. 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 consider the following objective functions: the makespan, the total completion time, the sum of the δth ( $ \delta \geqslant 0 $ ) power of job completion times, the total weighted completion time, the maximum lateness and the number of tardy jobs. We show that the makespan minimization problem, the total completion time minimization problem, and the sum of the δth power of job completion times minimization problem can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions.     

A note on single-machine total completion time problem with general deteriorating function

In this paper, we consider the single-machine scheduling problem with a deteriorating function. By the deteriorating function, we mean that the actual job processing time is a function of jobs already processed. We show that the total completion time minimization problem for a?≥?1 remains polynomially solvable under the proposed model, where a denotes the deterioration rate. For the case of 0?<?a?<?1, we show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to normal job processing times. We use the classical smallest processing time first rule as a heuristic algorithm for the case of 0?<?a?<?1 and analyze its worst-case bound.     

Single-machine group scheduling problems with deteriorating jobs

This paper investigates single-machine scheduling problems with deteriorating jobs and the group technology (GT) assumption. By deteriorating jobs and the group technology assumption, we mean that the group setup times and job processing times are both increasing functions of their starting times, i.e., the group setup times and job processing times are both described by a function which is proportional to a linear function of time. The two objectives of scheduling problems are to minimize the makespan and the total weighted completion time, respectively. We show that these problems remain solvable in polynomial time when deterioration and group technology are considered simultaneously.     

Lateral solutions for optimizing holding costs in job shops

Queuing networks present as beneficial models for a category of problems emerging in modern manufacturing systems. As the optimal control problem for queuing networks in familiar to be difficult, an important topic of research during the last two decades has been the growth of difficult estimations, and the use of these estimations to control optimal controls. Flexible moderations are an important class of such estimations that have received much consideration in recent years. The central objective of this paper is to determine the utilization of flexible moderations in solving a diversity of scheduling problems. In this paper, we investigate the role of flexible moderations in solving classic job shop problems. For the job shop problem with the objective of minimizing makespan, we build a schedule that is guaranteed to be within a consistent of the optimal. In other words, we examine the job shop scheduling problem with the aim of minimizing holding costs. Recent results show that for this objective, the job shop problem does not have a polynomial time estimation plan; consequently, in terms of approximability, this is a harder objective than the makespan. Our main result is an algorithm, based on regular relaxation that presents lateral optimal schedules.     

Single-machine group scheduling with linearly decreasing time-dependent setup times and job processing times

This paper considers single-machine scheduling problems with group technology (GT). We consider the case of group setup times and job processing times are a decreasing function of their starting time. We first prove that the makespan minimization problem remains polynomially solvable under the general decreasing linear deterioration. We then prove that the total weighted completion time minimization problem remains polynomially solvable under the proportional decreasing linear deterioration.     

Single-machine scheduling with a sum-of-processing-time based learning effect and deteriorating jobs

The paper deals with the single-machine scheduling problem with a sum-of-processing-time- based learning effect and deteriorating jobs. By the effects of sum-of-processing-time-based 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 the effects of sum-of-processing-time-based learning and deterioration to job processing times, the single-machine makespan minimization problem remains polynomially solvable.     

Some single-machine scheduling problems with past-sequence-dependent setup times and a general learning effect

This paper considers a single-machine scheduling model with past-sequence-dependent setup times and a general learning effect. It develops a general model with setup times and learning effect considerations where the actual processing time of a job is not only a function of the total actual processing time of the jobs already processed, but also a function of the job’s scheduled position. The paper shows that the single-machine scheduling problems to minimize the makespan and the sum of the kth power of completion times are polynomially solvable under the proposed model. It further shows that the problems to minimize the total weighted completion time and the maximum lateness are polynomially solvable under certain conditions.     

Note on “A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying activities on a single machine”

In this note, we study scheduling problems with simultaneous considerations of deteriorating jobs and rate-modifying activities on a single machine. The job-dependent deterioration effect and the job-independent deterioration effect models are examined with the objective of minimizing the makespan. We propose polynomial time solutions for all the studied problems.     

Single-machine scheduling with a time-dependent deterioration

The paper deals with the single-machine scheduling problems with a time-dependent deterioration. By time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. We show that, even with the introduction of time-dependent deterioration to job processing times, the single-machine makespan minimization problem remains polynomially solvable. We also show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to normal job processing times.     

Single machine scheduling with a learning effect and discounted costs

In this paper, we consider a single machine scheduling problem with a learning effect and discounted costs. The learning effect of a job is assumed to be a function of its position. We show that discounted total completion time is minimized by the classical shortest processing time first (SPT) rule. For the following objective function, discounted total weighted completion time, we show by an example that the optimal schedule of the classical discounted weighted shortest processing time first (WDSPT) rule is not optimal in the presence of a learning effect. But for some special cases, we prove that the WDSPT rule can construct the optimal sequence. We give the worst-case error bound for the WDSPT rule in the general case. Some extensions of the problem are also given.     

Single machine group scheduling with general linear deterioration to minimize the makespan

In this paper, we consider a single machine scheduling problem with deteriorating jobs and group technology assumption. By deteriorating jobs and group technology assumption, we mean that the group setup times and job processing times are both increasing functions of their starting times, i.e., group setup times and job processing times are both described by function, which is a general linear function of time. The objective of the scheduling problem is to minimize the makespan. We show that the problem remains solvable in polynomial time when general linear deterioration and group technology are considered simultaneously.     

Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan

In this paper, we consider an n-job, m-machine flow shop scheduling problem with deteriorating jobs. By deteriorating jobs, we mean jobs whose processing times are an increasing function of their execution starting time. A simple linear deterioration function is assumed. When some dominant relationships between m???1 machines can be satisfied, we show that the makespan minimization problem can be solved in polynomial time.     

Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach

In this study, we introduce a mixed nonlinear integer programming formulation for parallel machine earliness/tardiness (ET) scheduling 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 propose that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. The developed model allows sequence-dependent setups and sequence-dependent early/tardy penalties. The model can easily provide the optimal solution to problems involving about eleven jobs and two machines.     

Two-agent single-machine scheduling with position-dependent processing times

A new scheduling model in which both two-agent and position-dependent processing times exist simultaneously is considered in this paper. Two agents compete to perform their respective jobs on a common single machine, and each agent has his own criterion to optimize. The job position-dependent processing time is characterized by increasing or decreasing function dependent on the position of a job in the sequence. We introduce an aging effect and a learning effect into the two-agent single-machine scheduling, where the objective is to minimize the total completion time of the first agent with the restriction that the maximum cost of the second agent cannot exceed a given upper bound. We propose the optimal properties for the considered scheduling problems and then present the optimal polynomial time algorithms to solve the two scheduling problems, respectively.     

Two-agent group scheduling with deteriorating jobs on a single machine

This paper considers the two-agent scheduling problems with deteriorating jobs and group technology on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the maximum cost of the second agent cannot exceed a given upper bound. Two agents compete to perform their respective jobs on a common single machine, and each agent has his own criterion to optimize. We introduce deteriorating jobs and group technology into the two-agent single-machine scheduling where the job processing times and group setup times are both functions of their starting times. There are two different linear deterioration functions. We propose the optimal properties and present the optimal polynomial time algorithms for two different scheduling problems, respectively.     

Single machine rescheduling with new jobs arrivals and processing time compression

We consider job rescheduling problems where rescheduling is required in response to newly arriving jobs. To reduce the negative impacts of disruptions to the original schedule, the processing times of the newly arriving jobs can be reduced at a cost, which we call a time compression cost. The objective of the problem is to minimize total cost after rescheduling, which includes schedule disruption costs, time compression related costs, and a cost that depends on a traditional measure of schedule efficiency. We separately consider two different measures of schedule efficiency: total completion time and weighted tardiness, and present polynomial time algorithms for the total completion time case. For the weighted tardiness cost efficiency measure, we provide a heuristic based on very large scale neighborhood (VLSN) search.     

Scheduling with past-sequence-dependent setup times and learning effects on a single machine

In this paper, we study the single-machine scheduling problems with learning effect and setup time considerations. 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). The objective functions are to minimize the sum of the quadratic job completion times, the total waiting time, the total weighted completion time, the maximum lateness, the total absolute differences in waiting times, and the sum of earliness penalties subject to no tardy jobs, respectively. We show that the sum of the quadratic job completion times minimization problem, the total waiting time minimization problem, the total absolute differences in waiting times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs 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 some special cases.     

Flexible job shop scheduling with tabu search algorithms

This paper presents a tabu search algorithm that solves the flexible job shop scheduling problem to minimize the makespan time. As a context for solving sequencing and scheduling problems, the flexible job shop model is highly complicated. Alternative operation sequences and sequence-dependent setups are two important factors that frequently appear in various manufacturing environments and in project scheduling. In this paper, we present a model for a flexible job shop scheduling problem while considering those factors simultaneously. The purpose of this paper is to minimize the makespan time and to find the best sequence of operations and the best choice of machine alternatives, simultaneously. The proposed tabu search algorithm is composed of two parts: a procedure that searches for the best sequence of job operations, and a procedure that finds the best choice of machine alternatives. Randomly generated test problems are used to evaluate the performance of the proposed algorithm. Results of the algorithm are compared with the optimal solution using a mathematical model solved by the traditional optimization technique (the branch and bound method). After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented. Computational results indicate that the proposed algorithm can produce optimal solutions in a short computational time for small and medium sized problems. Moreover, it can be applied easily in real factory conditions and for large size problems. The proposed algorithm should thus be useful to both practitioners and researchers.     

On flowshop scheduling problems with the aging effect and resource allocation

In this paper, we focus on real-life settings that require the development of new models of flowshop scheduling problems, where job processing times can increase with the number of processed jobs due to the aging effect and decrease by the allocation of additional resource. We analyse the makespan minimization flowshop problem with such model and also with the aging effect only. We prove that the considered problems and their special cases are still polynomially solvable under given conditions, and on their basis, we provide optimal polynomial time solution algorithms.