Single machine scheduling problem with controllable processing times and resource dependent release times

We consider two single machine scheduling problems with resource dependent release times and processing times, in which the release times and processing times are linearly decreasing functions of the amount of resources consumed. The objective is to minimize the total cost of makespan and resource consumption function that is composed of release time reduction and processing time reduction. In the first problem, the cost of reducing a unit release time for each job is common. We show that the problem can be solved in polynomial time. The second problem assumes different reduction costs of job release times. We show that the problem can be reduced polynomially from the partition problem and thus, is NP-complete.     

Complexity of a scheduling problem with controllable processing times

We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.     

Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties

In this paper we consider identical parallel machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remain polynomially solvable under the proposed model.     

A survey of scheduling with controllable processing times

In classical deterministic scheduling problems, the job processing times are assumed to be constant parameters. In many practical cases, however, processing times are controllable by allocating a resource (that may be continuous or discrete) to the job operations. In such cases, each processing time is a decision variable to be determined by the scheduler, who can take advantage of this flexibility to improve system performance. Since scheduling problems with controllable processing times are very interesting both from the practical and theoretical point of view, they have received a lot of attention from researchers over the last 25 years. This paper aims to give a unified framework for scheduling with controllable processing times by providing an up-to-date survey of the results in the field.     

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 and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. 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 δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, 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.     

A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times

We present a unified analysis for single-machine scheduling problems in which the actual job processing times are controlled by either a linear or a convex resource allocation function and also vary concurrently depending on either the job’s position in the sequence and/or on the total processing time of the already processed jobs. We show that the problem is solvable in O(nlogn)$O(n\log n)$ time by using a weight-matching approach when a convex resource allocation function is in effect. In the case of a linear resource allocation function, we show that the problem can be solved in O(n³)$O(n^3)$ time by using an assignment formulation. Our approach generalizes the solution approach for the corresponding problems with controllable job processing times to incorporate the variability of the job processing times stemming from either the job’s position in the sequence and/or the total processing time of the already processed jobs.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS ： PROOF OF THEOREMS

This report is virtually the appendix part of the author‘s previous paper which ineludes the proofs for the theorems and lemmas.     

Single machine scheduling with total tardiness criterion and convex controllable processing times

We consider a single machine scheduling problem with total tardiness criteria and controllable job-processing times specified by a convex resource consumption function. The objective is to have the total tardiness limited into a given range, and minimize the total resource consumption. A polynomial time algorithm of O(n ²) is presented for the special case where jobs have a common due date.     

Single-machine scheduling with deteriorating functions for job processing times

In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier – this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by realloeating resources. In this paper, authors consider a machine scheduling problemwith controllable processing times. In the first part of this paper, a special case where the pro-cessing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O（n^2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case, An effective heuristic to the genera/ problem will be presented.     

Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect

In this paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, 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 randomly compressible processing times

This work is concerned with single machine scheduling with random compression of processing times. The objective is to find the optimal sequence to minimize the cost based on earliness, tardiness and compression. The analysis is carried out under a common due date. Both absolute derivation cost and squared derivation cost are considered. For both constrained problems and unconstrained problems, it is shown that an optimal schedule must be V-shaped. Remarks on common slack model is also provided.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （Part Ⅱ Heuristics for the General Case）

A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.     

Single machine scheduling with flow time and earliness penalties

This paper considers the problem of schedulingn jobs on a single machine to minimize the total cost incurred by their respective flow time and earliness penalties. It is assumed that each job has a due date that must be met, and that preemptions are not allowed. The problem is formulated as a dynamic program (DP) and solved with a reaching algorithm that exploits a series of dominance properties and efficiently generated bounds. A major factor underlying the effectiveness of the approach is the use of a greedy randomized adaptive search procedure (GRASP) to construct high quality feasible solutions. These solutions serve as upper bounds on the optimum, and permit a predominant portion of the state space to be fathomed during the DP recursion.To evaluate the performance of the algorithm, an experimental design involving over 240 randomly generated problems was followed. The test results indicate that problems with up to 30 jobs can be readily solved on a microcomputer in less than 12 minutes. This represents a significant improvement over previously reported results for both dynamic programming and mixed integer linear programming approaches.     

Single machine common flow allowance scheduling with controllable processing times

In this paper, we consider single machine SLK due date assignment scheduling problem in which job processing times are controllable variables with linear costs. The objective is to determine the optimal sequence, the optimal common flow allowance and the optimal processing time compressions to minimize a total penalty function based on earliness, tardiness, common flow allowance and compressions. We solve the problem by formulating it as an assignment problem which is polynomially solvable. For some special cases, we present an O(n logn) algorithm to obtain the optimal solution respectively.     

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.     

Dominance-based heuristics for one-machine total cost scheduling problems

We study the one-machine scheduling problem with release dates and we look at several objective functions including total (weighted) tardiness and total (weighted) completion time. We describe dominance rules for these criteria, as well as techniques for using these dominance rules to build heuristic solutions. We use them to improve certain well-known greedy heuristic algorithms from the literature. Finally, we introduce a Tabu Search method with a neighborhood based on our dominance rules. Experiments show the effectiveness of our techniques in obtaining very good solutions for all studied criteria.     

Scheduling two agents with controllable processing times

We consider several two-agent scheduling problems with controllable job processing times, where agents A and B have to share either a single machine or two identical machines in parallel while processing their jobs. The processing times of the jobs of agent A are compressible at additional cost. The objective function for agent B is always the same, namely a regular function _fmax$f_{\text{max}}$. Several different objective functions are considered for agent A, including the total completion time plus compression cost, the maximum tardiness plus compression cost, the maximum lateness plus compression cost and the total compression cost subject to deadline constraints (the imprecise computation model). All problems are to minimize the objective function of agent A subject to a given upper bound on the objective function of agent B. These problems have various applications in computer systems as well as in operations management. We provide NP-hardness proofs for the more general problems and polynomial-time algorithms for several special cases of the problems.