Search

In this paper, we investigate a single machine scheduling problem with a proportional job deterioration. Under release times (dates) of jobs, the objective is to minimize the total weighted completion time. For the general condition, some dominance properties, a lower bound and an upper bound are given, then a branch-and-bound algorithm is proposed. In addition, some meta-heuristic algorithms (including the tabu search ( T S ), simulated annealing ( S A ) and heuristic ( N E H ) algorithms) are proposed. Finally, experimental results are provided to compare the branch-and-bound algorithm and another three algorithms, which indicate that the branch-and-bound algorithm can solve instances of 40 jobs within a reasonable time and that the N E H and S A are more accurate than the T S . [ABSTRACT FROM AUTHOR]

Green scheduling that aims to enhance efficiency by optimizing resource allocation and job sequencing concurrently has gained growing academic attention. To tackle such problems with the consideration of scheduling and resource allocation, this paper considers a single-machine group scheduling problem with common/slack due-date assignment and a controllable processing time. The objective is to decide the optimized schedule of the group/job sequence, resource allocation, and due-date assignment. To solve the generalized case, this paper proves several optimal properties and presents a branch-and-bound algorithm and heuristic algorithms. Numerical experiments show that the branch-and-bound algorithm is efficient and the heuristic algorithm developed based on the analytical properties outruns the tabu search. [ABSTRACT FROM AUTHOR]

We study resource allocation scheduling with job-dependent learning effect on a single machine with or without due date assignment considerations. For a convex resource processing time function, we provide a polynomial time algorithm to find the optimal job sequence, and resource allocations that minimise the schedule criterion (the total compression cost) subject to the constraint that the total compression cost (the schedule criterion) is less than or equal to a fixed amount. [ABSTRACT FROM PUBLISHER]

This article addresses how to minimize total completion time on a single machine with a position-weighted learning effect. Under non-zero job release dates, a lower bound on the objective function, a number of dominance properties, and an initial solution (i.e. an NEH-based heuristic) are derived, which are used to expedite the elimination process of a branch-and-bound solution procedure. The performance of the branch-and-bound algorithm and the heuristic algorithm are evaluated on a set of randomly generated problem instances. [ABSTRACT FROM AUTHOR]

This article deals with a single-machine resource allocation scheduling problem with deteriorating jobs. Under a group technology environment, the actual processing times of jobs are a convex resource allocation function of their starting time and the amount of resource allocation. The objective is to minimize the weighted sum of makespan and resource allocation cost. For two special cases, it is proved that the problem can be solved in polynomial time. For the general case of the problem, heuristic and branch-and-bound procedures are developed to solve the problem. Computational experiments are also performed to examine the effectiveness and the efficiency of the algorithms. [ABSTRACT FROM AUTHOR]

The note deals with machine scheduling problems with a more general learning effect model, i.e., the actual job processing time is a function of the sum of the function of the processing times of the jobs already processed and job position. We show that some single machine scheduling problems are still polynomially solvable under the proposed model. We also show that some special cases of the flow shop scheduling problems can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

This paper deals with single machine scheduling problems with simple linear deterioration in which the processing time of a job is a simple linear function of its execution starting time. The objective is to determine the optimal schedule to minimize the weighted sum of the θ th ( θ is a positive integer number) power of waiting times. It is proved that the general problem can be solved in polynomial time. In addition, for the jobs with weak (strong) parallel chains and a series–parallel digraph precedence constraints, it is also proved that these problems can be solved in polynomial time, respectively. [ABSTRACT FROM AUTHOR]

Abstract: The paper deals with machine scheduling problems with a general learning effect. By the general learning effect, we mean that the actual processing time of a job is not only a non-increasing function of the total weighted normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence, where the weight is a position-dependent weight. We show that even with the introduction of a general learning effect to job processing times, some single machine scheduling problems are still polynomially solvable under the proposed model. We also show that some special cases of the flow shop scheduling problems can be solved in polynomial time. [Copyright &y& Elsevier]

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of −1 < a < 0, where a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper we consider a single-machine common due-window assignment scheduling problem with learning effect and deteriorating jobs. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, window size, earliness and tardiness. We show that the problem remains polynomially solvable under the proposed model. [Copyright &y& Elsevier]

Abstract: 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. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we show that the main results in a recent paper by Zhang and Yan [X. Zhang and G. Yan, Machine scheduling problems with a general learning effect, Mathematical and Computer Modelling 51 (2010) 84–90] are incorrect as an important reason is missing, that is, the processing time of a job is variable according to a general learning effect. Here we point out these wrong results by a counter-example. In addition, we give a revised model with a general learning effect. We show that some single machine scheduling problems are still polynomially solvable under the revised model. We also show that some special cases of the flowshop scheduling problems can be solved in polynomial time under the revised model. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the problem of simultaneous determination of optimal due dates and optimal schedule for the single machine problem with multiple common due dates. The penalty for a job is assumed to be a linear function of the due date and the earliness/tardiness for the job. The objective function is to minimize the total penalty for all jobs. We show that with the introduction of learning to job processing times the problem remains polynomially solvable for a given number of multiple common due dates. [Copyright &y& Elsevier]

Abstract: In this paper we consider single-machine scheduling problems with an exponential sum-of-actual-processing-time-based learning effect. By the exponential sum-of-actual-processing-time-based learning effect, we mean that the processing time of a job is defined by an exponential function of the sum of the actual processing times of the already processed jobs. For the proposed learning model, we show that under certain conditions, the makespan minimization problem, the sum of the th () powers of completion times minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem all remain polynomially solvable. [ABSTRACT FROM AUTHOR]

Abstract: This paper considers single machine scheduling problems with group technology (GT) and deteriorating jobs. We consider the case of jobs whose processing times are a simple linear function of their starting time. The two objectives of scheduling problems are to minimize the weighted sum of squared completion times and the weighted sum of squared waiting times, respectively. We also provide polynomial time algorithms to solve these problems. [Copyright &y& Elsevier]

Abstract: In this paper we consider the single-machine scheduling problems with job-position-based and sum-of-processing-times based processing times. The real processing time of a job is a function of its position and the total processing time of the jobs that are in front of it in the sequence. The objective is to minimize the makespan, and to minimize the mean finish time. We prove that some special cases are polynomially solvable under some restrictions of the parameters. In addition, for some another special cases of minimization of the mean finish time and the makespan, we show that an optimal schedule is V-shaped with respect to job normal processing times. Then, we propose a heuristic based on the V-shaped property, and show through a computational experiment that it performs efficiently. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: In this study we consider the single-machine scheduling problems with a sum of-processing-times-based learning effect. The sum of-processing-times-based learning effect of a job is assumed to be a function of the sum of the normal processing time of the already processed jobs. The objective is to minimize one of two regular objective functions, namely the weighted sum of completion times and the maximum lateness. We use the weighted shortest processing time (WSPT) rule and the earliest due date (EDD) rule as heuristics for the general cases and analyze their worst-case error bounds. We also provide computational results to evaluate the performance of the heuristics. [Copyright &y& Elsevier]

Abstract: In this paper we consider a single-machine scheduling problem with the effects of learning and deterioration. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of earliness, tardiness and due-date. We show that the problem remains polynomially solvable under the proposed model. [Copyright &y& Elsevier]

Abstract: This paper studies the single machine scheduling problems with learning effect and deteriorating jobs simultaneously. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, the makespan, the total completion time and the sum of the th power of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions: the total weighted completion time and the maximum lateness, this paper proves that the shortest weighted processing time first (WSPT) rule and the earliest due-date first (EDD) rule can construct the optimal sequence under some special cases, respectively. [Copyright &y& Elsevier]

Abstract: This paper deals with single-machine scheduling problems with decreasing linear deterioration, i.e., jobs whose processing times are a decreasing function of their starting times. 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. [Copyright &y& Elsevier]

Abstract: In this paper we consider the single machine scheduling problem with exponential time-dependent learning effect and past-sequence-dependent (p-s-d) setup times. By the exponential time-dependent learning effect, we mean that the processing time of a job is defined by an exponent function of the total normal processing time of the already processed jobs. 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 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. [Copyright &y& Elsevier]

Two single machine scheduling problems with a learning effect are considered. The learning effect of a job is assumed to be a function of its position. For the following two objective functions: the weighted sum of completion times and the maximum lateness, it is shown that the weighted shortest processing time first (WSFT) rule and the earliest due date first (EDD) rule can construct the optimal sequence for some special cases, respectively. The worst case error bounds for these two rules in general cases are also given. [ABSTRACT FROM AUTHOR]

Abstract: In this study we consider the single-machine scheduling problem with a sum-of-processing-times-based learning effect. The sum-of-processing-times-based learning effect of a job is assumed to be a function of the sum of the normal processing times of the already processed jobs. We prove that the shortest processing time (SPT) rule is optimal for the sum of completion times square minimization problem. We also show by examples that the optimal schedule for the classical version of the problem is not optimal in the presence of a sum-of-processing-times-based learning effect for the following three objective functions: the weighted sum of completion times, the maximum lateness and the number of tardy jobs. But for some special cases, we prove that the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and Moore’s algorithm can construct an optimal schedule for the problem to minimize these objective functions, respectively. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a single machine scheduling problem with a common due date. Job processing times are controllable to the extent that they can be reduced, up to a certain limit, at a cost proportional to the reduction. The common due date, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the common due date, processing time reduction as well as job absolute value in lateness. We show that the problem can be formulated as an assignment problem and thus can be solved with well-known algorithms. For the case that where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution. [Copyright &y& Elsevier]