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.     

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

Scheduling jobs on parallel machines with setup times and ready times

In this research we are interested in scheduling jobs with ready times on identical parallel machines with sequence dependent setups. Our objective is to minimize the total weighted tardiness. As this problem is NP-Hard, we develop a heuristic to solve this problem in reasonable time. Our approach is an extension of the apparent tardiness cost with setups (ATCS) approach by [Lee, Y. H., Pinedo, M. (1997). Scheduling jobs on parallel machines with sequence dependent setup times. European Journal of Operational Research, 100, 464–474.] to allow non-ready jobs to be scheduled – meaning we allow a machine to remain idle for a high priority job arriving at a later time. To determine the scaling parameters for our composite dispatching rule (called ATCSR), we first develop a ‘grid approach’ that considers multiple values for the scaling parameters, generates multiple schedules, and chooses the best schedule for the solution. This experimentation was then used to develop regression equations to predict the values of the scaling parameters that would yield the highest quality solution. The grid and regression versions of ATCSR provide better performance than grid and empirically based formula versions of ATCS, BATCS, and X-RM which are the prominent algorithms in the literature.     

Scheduling deteriorating jobs on a single machine with release times

This paper investigates a single-machine deteriorating job scheduling problem with job release times where its objective is to minimize the makespan. The problem is known to be NP-hard. Therefore, a branch-and-bound algorithm incorporating with several dominance properties and lower bounds is proposed to derive the optimal solution for the problem. In addition, easy-implemented heuristic algorithms are also provided to obtain the near-optimal solution. The computational experiments indicate that the branch-and-bound algorithm can solve most of the medium-job-sized problems within a reasonable time, and the heuristic is quite accurate with an average error percentage of less than 0.3%.     

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.     

Single-machine group scheduling with both learning effects and deteriorating jobs

In the paper two resource constrained single-machine group scheduling problems with both learning effects and deteriorating jobs are considered. By learning effects, deteriorating jobs and group technology assumption, we mean that the processing time of a job is defined by the function of its starting time and position in the group, and the group setup times of a group is a positive strictly decreasing continuous function of the amount of consumed resource. We present polynomial solutions for the makespan minimization problem under the constraint that the total resource consumption does not exceed a given limit, and the total resource consumption minimization problem under the constraint that the makespan does not exceed a given limit, respectively.     

Scheduling with multi-attribute setup times

In this paper we address a scheduling problem with multi-attribute setup times originated from the manufacturing plant of a company producing PVC sheets. In the considered scheduling problem, each job has a number of attributes and each attribute has one or more levels. Because there is at least one different level of attribute between two adjacent jobs, it is necessary to make a setup adjustment whenever there is a switch to a different job. The objective of the problem is to determine a processing sequence so as to minimize the total setup time on a single machine.     

Scheduling jobs with simultaneous considerations of controllable processing times and learning effect

This paper considers a scheduling problem with general job-dependent learning curves and controllable processing times on a single machine. The objective is to determine the optimal compressions of the processing times and the optimal sequence of jobs so as to minimize some total cost functions, which consist of regular and non-regular functions and the processing time compressions. It shows that the problem can be solved by an assignment problem and thus can be solved in polynomial time. Some extensions of the problem are also given.

     

Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times

The single-machine scheduling problem with truncated sum-of-processing-times-based learning effect and past-sequence-dependent job delivery times is considered. Each job’s delivery time depends on its waiting time of processing. For some regular objective functions, it is proved that the problems can be solved by the smallest processing time first rule. For some special cases of the total weighted completion time and the maximum lateness objective functions, the thesis shows that the problems can be solved in polynomial time.     

Resource-dependent scheduling with deteriorating jobs and learning effects on unrelated parallel machine

The focus of this paper is to analyze unrelated parallel-machine resource allocation scheduling problem with learning effect and deteriorating jobs. The goal is to find the optimal sequence of jobs and the optimal resource allocation separately for minimizing the cost function including the total load, the total completion time, the total absolute deviation of completion time and the total resource cost. We show that the problem is polynomial time solvable if the number of machines is a given constant.     

Scheduling linearly deteriorating jobs on multiple machines

This paper investigates the scheduling problems in which the job processing times do not remain constant but are increasing linear functions of their starting times. Two deteriorating scheduling models, Model 1 and Model 2, for multiple machines are considered, with the goal being to minimize the makespan. In this paper, we propose an efficient heuristic for Model 1 and prove that the ratio of the makespan obtained by the heuristic to the optimal makespan is bounded. For Model 2, three heuristics, including a probabilistic heuristic, are proposed for minimizing the makespan. Numerical results are provided to show the efficiency of the approaches in this paper.     

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.     

A note on optimal policies for two group scheduling problems with deteriorating setup and processing times

Conventionally, job processing times are known and fixed. However, there are many situations where the job processing time deteriorates as time passes. In this note, we consider the makespan problems under the group technology with deteriorating setup and processing times. That is, the job processing times and group setup times are linearly increasing (or decreasing) functions of their starting times. For both linear functions, we show that the makespan problems remain polynomially solvable. In addition, the constructive algorithms are also provided.     

Scheduling problems with partially ordered jobs

Scheduling problems with given precedence constraints (with partially ordered jobs) are considered. A review of the results obtained in this area by the members of Minsk Scheduling Theory school created by V.S. Tanaev is done.     

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.     

Single-machine scheduling with past-sequence-dependent setup times and learning effects: a parametric analysis

In this article, we consider the single-machine scheduling problem with past-sequence-dependent (p-s-d) setup times and a learning effect. The setup times are proportional to the length of jobs that are already scheduled; i.e. p-s-d setup times. The learning effect reduces the actual processing time of a job because the workers are involved in doing the same job or activity repeatedly. Hence, the processing time of a job depends on its position in the sequence. In this study, we consider the total absolute difference in completion times (TADC) as the objective function. This problem is denoted as 1/LE, s _psd /TADC in Kuo and Yang (2007 Kuo, WH and Yang, DL. 2007. Single Machine Scheduling with Past-sequence-dependent Setup Times and Learning Effects. Information Processing Letters, 102: 22–26. [Crossref], [Web of Science ®] , [Google Scholar]) (‘Single Machine Scheduling with Past-sequence-dependent Setup Times and Learning Effects’, Information Processing Letters, 102, 22–26). There are two parameters a and b denoting constant learning index and normalising index, respectively. A parametric analysis of b on the 1/LE, s _psd /TADC problem for a given value of a is applied in this study. In addition, a computational algorithm is also developed to obtain the number of optimal sequences and the range of b in which each of the sequences is optimal, for a given value of a. We derive two bounds b* for the normalising constant b and a* for the learning index a. We also show that, when a?a* or b?>?b*, the optimal sequence is obtained by arranging the longest job in the first position and the rest of the jobs in short processing time order.     

Single-machine scheduling with deteriorating jobs

In this article, we study a single-machine scheduling problem in which the processing time of a job is a nonlinear function of its basic processing time and starting time. The objectives are to minimise the makespan, the sum of weighted completion times and the sum of the kth powers of completion times. We show that the makespan minimisation problem can be solved in polynomial time. However, the total completion time and the sum of the kth powers of completion times minimisation problems can be solved in polynomial time in some cases. Besides, some useful properties are also provided for the sum of weighted completion times problem under certain conditions.