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 past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects

This paper studies the single machine past-sequence-dependent (p-s-d) delivery times scheduling 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. We consider the following objective functions: the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?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 minimization of the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?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 discounted total weighted completion time minimization problem, the maximum lateness minimization problem, the maximum tardiness minimization problem and the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times

This paper considers single machine scheduling with past-sequence-dependent (psd) delivery times, in which the processing time of a job depends on its position in a sequence. We provide a unified model for solving single machine scheduling problems with psd delivery times. We first show how this unified model can be useful in solving scheduling problems with due date assignment considerations. We analyze the problem with four different due date assignment methods, the objective function includes costs for earliness, tardiness and due date assignment. We then consider scheduling problems which do not involve due date assignment decisions. The objective function is to minimize makespan, total completion time and total absolute variation in completion times. We show that each of the problems can be reduced to a special case of our unified model and solved in O(n ³) time. In addition, we also show that each of the problems can be solved in O(nlogn) time for the spacial case with job-independent positional function.     

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

Scheduling with learning effect and deteriorating jobs has become more popular. However, most of the research assume that the setup time is negligible or a part of the job processing time. In this paper, we propose a model where the deteriorating jobs, the learning effect, and the setup times are present simultaneously. Under the proposed model, the setup time is past-sequence-dependent and the actual job processing time is a general function of the processing times of the jobs already processed and its scheduled position. We provide the optimal schedules for some single-machine problems.     

Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning

In this paper we consider the single-machine setup times scheduling with general effects of deterioration and learning. By the general effects of deterioration and learning, we mean that the actual job processing time is a general function of the processing times of the jobs already processed and 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 sum of the δ$\delta$th (δ>0$\delta >0$) power of job completion times, the total lateness are polynomially solvable. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness (tardiness) minimization problem, the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Erratum to “Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects” [Appl. Math. Modell. 35 (2011) 1388–1395]

The aim of this paper is to show by a counterexample that Theorem 7 and Corollary 8 in Wang and Li [Appl. Math. Modell. 35 (2011) 1388–1395.] are incorrect.     

Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects

In this article, 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 objective is to minimize the total completion time. We show that there exists a polynomial time solution for the proposed problem. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.     

Single-machine scheduling problems with past-sequence-dependent setup times

This paper studies single-machine scheduling problems with setup times which are proportionate to the length of the already scheduled jobs, that is, with past-sequence-dependent or p-s-d setup times. The following objective functions are considered: the maximum completion time (makespan), the total completion time, the total absolute differences in completion times and a bicriteria combination of the last two objective functions. It is shown that the standard single-machine scheduling problem with p-s-d setup times and any of the above objective functions can be solved in O(nlog n) time (where n is the number of jobs) by a sorting procedure. It is also shown that all of our results extend to a “learning” environment in which the p-s-d setup times are no longer linear functions of the already elapsed processing time due to learning effects.     

Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times

This paper considers single-machine scheduling problems with job delivery times where the actual job processing time of a job is defined by a function dependent on its position in a schedule. We assume that the job delivery time is proportional to the job waiting time. We investigate the minimization problems of the sum of earliness, tardiness, and due-window-related cost, the total absolute differences in completion times, and the total absolute differences in waiting times on a single-machine setting. The polynomial time algorithms are proposed to optimally solve the above objective functions. We also investigate some special cases of the problem under study and show that they can be optimally solved by lower order algorithms.     

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

In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier – this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.     

Single-machine scheduling against due dates with past-sequence-dependent setup times

Recently Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] introduced past-sequence-dependent setup times to scheduling problems. This means that the setup time of a job is proportionate to the sum of processing times of the jobs already scheduled. Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] were able to show for a number of single-machine scheduling problems with completion time goals that they remain polynomially solvable. In this paper we extend the analysis to problems with due dates. We demonstrated that some problems remain polynomially solvable. However, for some other problems well-known polynomially solution approaches do not guarantee optimality any longer. Consequently we concentrated on finding polynomially solvable special cases.     

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.     

Single machine scheduling with time-dependent linear deterioration and rate-modifying maintenance

We study single machine scheduling problems with linear time-dependent deterioration effects and maintenance activities. Maintenance periods (MPs) are included into the schedule, so that the machine, that gets worse during the processing, can be restored to a better state. We deal with a job-independent version of the deterioration effects, that is, all jobs share a common deterioration rate. However, we introduce a novel extension to such models and allow the deterioration rates to change after every MP. We study several versions of this generalized problem and design a range of polynomial-time solution algorithms that enable the decision-maker to determine possible sequences of jobs and MPs in the schedule, so that the makespan objective can be minimized. We show that all problems reduce to a linear assignment problem with a product matrix and can be solved by methods very similar to those used for solving problems with positional effects.     

Single machine batch scheduling with resource dependent setup and processing times

Jobs are processed by a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource, which may be different from that for the jobs. Polynomial time algorithms are presented to find an optimal batch sequence and resource values such that either the total weighted resource consumption is minimized, subject to meeting job deadlines, or the maximum job lateness is minimized, subject to an upper bound on the total weighted resource consumption. The algorithms are based on linear programming formulations of the corresponding problems.     

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 group scheduling with resource dependent setup and processing times

A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques.     

Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine

This paper deals with serial-batching scheduling problems with the effects of deterioration and learning, where time-dependent setup time is also considered. In the proposed scheduling models, all jobs are first partitioned into serial batches, and then all batches are processed on a single serial-batching machine. The actual job processing time is a function of its starting time and position. In addition, a setup time is required when a new batch is processed, and the setup time of the batches is time-dependent, i.e., it is a linear function of its starting time. Structural properties are derived for the problems of minimizing the makespan, the number of tardy jobs, and the maximum earliness. Then, three optimization algorithms are developed to solve them, respectively.     

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.     

Bi-criteria single machine scheduling with a time-dependent learning effect and release times

This paper deals with a bi-criteria single machine scheduling problem with a time-dependent learning effect and release times. The objective is to minimize the weighted sum of the makespan and the total completion time. The problem is NP-hard, thus a mixed integer non-linear programming formulation is presented, and a set of dominance properties are developed. To solve the problem efficiently, a procedure is then proposed by incorporating the dominance properties with an ant colony optimization algorithm. In the proposed algorithm, artificial ants construct solutions as orders of jobs based on the heuristic information as well as pheromone trails. Then, the dominance properties are added to obtain better solutions. To evaluate the algorithm performance, computational experiments are conducted.