Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties

We consider a single-machine scheduling problem with linear decreasing deterioration in which the due dates are determined by the equal slack (SLK) method. By the linear decreasing deterioration, we mean that the job’s processing time is a decreasing function of its starting time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function.     

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 with time-and-resource-dependent processing times

We consider single-machine scheduling problems in which the processing time of a job is a function of its starting time and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We show that the problems remain polynomially solvable under the proposed model.     

Processing-plus-wait due dates in single-machine scheduling

We study the problem of schedulingn jobs on a single machine. Each job is assigned a processing-plus-wait due date, which is an affine-linear function of its processing time. The objective is to minimize the symmetric earliness and tardiness costs. We analyze a combined decision model which includes computing both the optimal job sequence and optimal due date parameters. For the quadratic objective function, we propose a heuristic solution based on a bicriterion approach. Additionally, we provide computational results to compare this model with two simpler models. For the maximum objective function, we show that it is efficiently solved by the shortest processing time sequence.Part of this research was undertaken during a visit of the first author at the University of Manitobe, Canada in 1991. This visit was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The numerical results were obtained with the assistance of T. P. Lindenthal. The authors are thankful for his help.     

Single-machine scheduling with learning and forgetting effects

Scheduling with learning effects has been widely studied in the past decade. With the increasingly moving toward shorter product cycle times in many production lines, workers in this changeable environment must constantly learn new skill and technology. As a result, the forgetting effect might occur in these situations. In this paper, we propose a model with the consideration of both the learning and forgetting effects. We show some single-machine problems remain polynomially solvable under the proposed model.     

Single-machine scheduling with a general sum-of-actual-processing-times-based and job-position-based learning effect

In this paper, we bring into the scheduling field a general learning effect model where the actual processing time of a job is not only a general function of the total actual processing times of the jobs already processed, but also a general function of the job’s scheduled position. We show that the makespan minimization problem and the sum of the kth power of completion times minimization problem 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 certain conditions.     

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 problems with a learning effect

In many situations, the skills of workers continuously improve when repeating the same or similar tasks. This phenomenon is known as the “learning effect” in the literature. In most studies, the learning phenomenon is implemented by assuming the actual job processing time is a function of its scheduled position [D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res. 115 (1999) 173–178]. Recently, a new model is proposed where the actual job processing time depends on the sum of the processing times of jobs already processed [C. Koulamas, G.J. Kyparisis, Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res. 178 (2007) 402–407]. In this paper, we extend their models in which the actual job processing time not only depends on its scheduled position, but also depends on the sum of the processing times of jobs already processed. We then show that the single-machine makespan and the total completion time problems remain polynomially solvable under the proposed model. In addition, we show that the total weighted completion time has a polynomial optimal solution under certain agreeable solutions.     

Single-machine scheduling with effects of exponential learning and general deterioration

The purpose of this study is to explore the single-machine scheduling with the effects of exponential learning and general deterioration. By the effects of exponential learning and general deterioration, we meant that job processing time is decided by the functions of their starting time and positions in the sequence. Results showed that with the introduction of learning effect and deteriorating jobs to job processing time, single-machine makespan, and sum of completion time (square) minimization problems remained polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion time and the maximum lateness, this paper proved that the weighted smallest basic processing time first (WSPT) rule and the earliest due date first (EDD) rule constructed the optimal sequence under some special cases, respectively.     

Single-machine scheduling with convex resource dependent processing times and deteriorating jobs

In this study, we consider scheduling problems with convex resource dependent processing times and deteriorating jobs, in which the processing time of a job is a function of its starting time and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately. This paper focus on the single-machine problems with objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. It shows that the problems remain polynomially solvable under the proposed model.     

A unified approach for scheduling with convex resource consumption functions using positional penalties

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n³)$O(n^3)$ time. Furthermore, we show how the unified model can be used repeatedly as a subroutine to solve all problems from the second group in O(n⁴)$O(n^4)$ time. In addition, we also show that faster algorithms exist for several special cases.     

Single-machine scheduling with precedence constraints and position-dependent processing times

In this paper we consider single-machine scheduling problems with position-dependent processing times, i.e., jobs whose processing times are an increasing or decreasing function of their positions in a processing sequence. In addition, the jobs are related by parallel chains and a series–parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan polynomial algorithms exist.     

Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan

This paper studies the single-machine scheduling problem with deteriorating jobs and learning considerations. The objective is to minimize the makespan. We first show that the schedule produced by the largest growth rate rule is unbounded for our model, although it is an optimal solution for the scheduling problem with deteriorating jobs and no learning. We then consider three special cases of the problem, each corresponding to a specific practical scheduling scenario. Based on the derived optimal properties, we develop an optimal algorithm for each of these cases. Finally, we consider a relaxed model of the second special case, and present a heuristic and analyze its worst-case performance bound.     

Single-machine scheduling with waiting-time-dependent due dates

We consider a single-machine scheduling problem in which due dates are linear functions of the job waiting-times and the objective is to minimize the maximum lateness. An optimal sequence is constructed by implementing an index-based priority rule for a fixed value of the due date normalizing constant k. We determine in polynomial time all the k value ranges so that the optimal sequence remains the same within each range. The optimal due dates are computed as linear functions of the global optimal value of k. The overall procedure is illustrated in a numerical example.     

A sequential exchange approach for minimizing earliness–tardiness penalties of single-machine scheduling with a common due date

This study focuses on a class of single-machine scheduling problems with a common due date where the objective is to minimize the total earliness–tardiness penalty for the jobs. A sequential exchange approach utilizing a job exchange procedure and three previously established properties in common due date scheduling was developed and tested with a set of benchmark problems. The developed approach generates results better than not only those of the existing dedicated heuristics but also in many cases those of meta-heuristic approaches. And the developed approach performs consistently well in various job settings with respect to the number of jobs, processing time and earliness–tardiness penalties for the jobs.     

Single-machine group scheduling with processing times dependent on position,starting time and allotted resource

This article considers scheduling problems on a single machine with learning effect, deteriorating jobs and resource allocation under group technology (GT) assumption. We assume that the actual processing time of a job depends on the job position, the group position, the starting time and the amount of resource allocated to them concurrently, and the actual setup times of groups depend on the group position and the amount of resource allocated to them concurrently. Two resource allocation functions are examined for minimizing the weighted sum of makespan and total resource cost. We prove that the problems have polynomial solutions under the condition that the number of jobs in each group are the same.     

工件具有加工位置上限最小化加权总误工量的单机排序问题

考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中,每个工件J_j都具有一个加工位置上限k_j.也就是说,如果工件J_j是一个可行排序中的第x个工件,那么就需要满足x ≤ k_j.证明了（i）当工件具有相同工期时,该排序问题是二元NP-难的并且是拟多项式时间可解的,（ii）当工件具有单位权重时,该排序问题是一元NP-难的.     

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.     

Two due date assignment problems in scheduling a single machine

We study two single-machine scheduling problems: minimizing the sum of weighted earliness, tardiness and due date assignment penalties and minimizing the weighted number of tardy jobs and due date assignment costs. We prove that both problems are strongly NP-hard and give polynomial solutions for some important special cases.