Search

In this paper, we study scheduling with step-learning, i.e., a setting where the processing times of the jobs started after their job-dependent learning-dates are reduced. The goal is to minimize makespan on a single machine. We focus first on the case that idle times between consecutive jobs are not allowed. We prove that the problem is NP-hard, implying that no polynomial-time solution exists and, consequently, propose a pseudo-polynomial time dynamic programming algorithm. An extensive numerical study is provided to examine the running time of the algorithm with different learning-dates and job processing time ranges. The special case of a common learning-date for all the jobs is also studied, and a (more efficient) pseudo-polynomial dynamic programming is introduced and tested numerically. In the last part of the paper, the more complicated setting in which idle times are allowed is studied. An appropriate dynamic programming is introduced and tested as well. [ABSTRACT FROM AUTHOR]

In this paper, we address single-machine scheduling with sum of logarithm processing times-based learning effect. Under exponential past-sequence-dependent delivery times, we proved that the makespan and total completion time minimizations can be solved by the smallest processing time (SPT) first rule. Under the agreeable weight condition and agreeable due date condition, we show that the total weighted completion time minimization and maximum tardiness minimization can be solved in polynomial time, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we examined single and parallel machine scheduling problems with a learning effect and job rejection simultaneously. In real life, job processing times decrease when there is a learning effect. In some cases, producers cannot process all the jobs and pay the penalty cost for these jobs that they do not process. In our study, learning effect and job rejection are considered at the same time. We examined four different objective functions. Our objectives for single-machine scheduling problems are makespan and rejection cost minimization, total completion time and rejection cost minimization and total absolute deviation of completion times (TADC) and rejection cost minimization. Our objective for parallel machines is makespan and rejection cost minimization. The problems are solved by mathematical models, and four different algorithms are proposed for the problems. From these algorithms, the same results are obtained with single-machine makespan and rejection cost minimization, parallel machine makespan and rejection cost minimization and total completion time and rejection cost minimization. The accuracy for these models is obtained as 100%. The proposed algorithm for TADC and rejection cost minimization yielded close-to-optimal results. Mathematical model and algorithm results for 10 jobs, 20 jobs and 30 jobs are compared and the results are presented. The obtained solutions are obtained in polynomial time. [ABSTRACT FROM AUTHOR]

We consider single-machine scheduling problems with a batch-dependent ageing effect and variable maintenance activities between batches. The machine can process several jobs as a batch. It requires maintenance activities where the maintenance time depends on the flow time of the pre-batch, i.e. the batch processed before a batch. A job's actual processing time is an increasing exponential function of its operation time within a batch. The objectives are to minimise the makespan and the total completion time. We develop polynomial time algorithms for the makespan minimisation problem and the total completion time minimisation problem under the condition that the ageing factor is greater than one. We also provide a mathematical programming approach and two heuristic algorithms to analyse the total completion time minimisation problem when the ageing factor is less than one for even one batch. The computational analysis indicates that the proposed heuristic algorithms are more efficient for the smaller ageing factor, whereas the Modified Shortest Processing Time algorithm is more efficient than the proposed heuristic algorithms for the larger ageing factor. [ABSTRACT FROM AUTHOR]

In the literature on multi-scenario scheduling problems, it is assumed that (i) each scenario defines a different possible realization of the job's parameters; and (ii) the value of each parameter is arbitrary for any job in any scenario. Under these assumptions many multi-scenario scheduling problems have been proven to be NP -hard. We study a special case of this set of problems, in which there is an agreeable condition between scenarios on the processing-time parameters. Accordingly, the processing time of job J j under scenario s i is at most its value under scenario s i + 1 , for i = 1 , ... q - 1 , where q is the number of different possible scenarios. We focus on three classical scheduling problems for which the single-scenario case is solvable in polynomial time, while the multi-scenario case is NP -hard, even when there are only two scenarios. The three scheduling problems consist of minimizing either the total completion time or the number of tardy jobs on a single machine, and minimizing the makespan in a two-machine flow-shop system. We show that the multi-scenario version of all three problems remains NP -hard even when processing times are agreeable and there are only two scenarios. We also show that for a more specific structure of job processing times two out of the three problems become easy to solve, while the complexity status of the third remains open for future research. [ABSTRACT FROM AUTHOR]

We consider a single-machine bi-objective scheduling problem with rejection. In this problem, it is possible to reject some jobs. Four algorithms are provided to solve this scheduling problem. The two objectives are the total weighted completion time and the total rejection cost. The aim is to determine the set of efficient solutions. Four heuristics are described; they are implicit enumeration algorithms forming a branching tree, each one having two versions according to the root of the tree corresponding either to acceptance or rejection of all the jobs. The algorithms are first illustrated by a didactic example. Then they are compared on a large set of instances of various dimension and their respective performances are analysed.

The paper studies the single-machine scheduling problem with sequence-dependent setup times under dynamic environment. In this problem, jobs arrive over time and all the information on a job is unknown in advance. The objective is to find a feasible schedule such that the maximum lateness is minimised. This problem represents a very important production scheduling problem but remains under-represented in the literature. To solve the problem, we propose a dynamic differential evolution algorithm that considers the new environment and the previous environment simultaneously. The performance of the algorithm is enhanced by two heuristics for generating efficient initial solutions, a local search procedure and a speed-up method. To evaluate its performance, the proposed algorithm is tested on 1000 instances from the literature. The computational results demonstrate that the proposed algorithm is highly effective as compared to the methods known from the literature. [ABSTRACT FROM AUTHOR]

This paper considers a single-machine scheduling problem with deteriorating jobs and convex resource allocation. We assume that the actual processing time of a job is a function of its convex resource allocation and its starting time. For the multi-objective single-machine scheduling problem, we show that the problem is polynomially solvable in O (n log n) time, where n is the total number of jobs. [ABSTRACT FROM AUTHOR]

This paper introduces the serial batching scheduling problems with position-based learning effect, where the actual job processing time is a function of its position. Two scheduling problems respectively for single-machine and parallel-machine are studied, and in each problem the objectives of minimizing maximum earliness and total number of tardy jobs are both considered respectively. In the proposed scheduling models, all jobs are first partitioned into serial batches, and then all batches are processed on the serial-batching machine. We take some practical production features into consideration, i.e., setup time before processing each batch increases with the time, regarded as time-dependent setup time, and we formalize it as a linear function of its starting time. Under the single-machine scheduling setting, structural properties are derived for the problems with the objectives of minimizing maximum earliness and number of tardy jobs respectively, based on which optimization algorithms are developed to solve them. Under the parallel-machine scheduling setting, a hybrid VNS-GSA algorithm combining variable neighborhood search (VNS) and gravitational search algorithm (GSA) is proposed to solve the problems with these two objectives respectively, and the effectiveness and efficiency of the proposed VNS-GSA are demonstrated and compared with the algorithms of GSA, VNS, and simulated annealing (SA). This paper demonstrates that the consideration of different objectives leads to various optimal decisions on jobs assignment, jobs batching, and batches sequencing, which generates a new insight to investigate batching scheduling problems with learning effect under single-machine and parallel-machine settings. [ABSTRACT FROM AUTHOR]

The paper deals with resource allocation scheduling problems in which the processing time of a job is defined by a function of its starting times and its position in a sequence. We also assume that the resource-dependent ready times of jobs are continuous functions of their consumed resource. Our objective is to minimize the resource consumption (the makespan) subject to the makespan constraint (limited resource availability). We prove that these two single-machine scheduling problems can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

Rescheduling in production planning means to schedule the sequenced jobs again together with a set of new arrived jobs so as to generate a new feasible schedule, which creates disruptions to any job between the original and adjusted position. In this paper, we study rescheduling problems with learning effect under disruption constraints to minimize several classical objectives, where learning effect means that the workers gain experience during the process of operation and make the actual processing time of jobs shorter than their normal processing time. The objectives are to find optimal sequences to minimize the makespan and the total completion time under a limit of the disruptions from the original schedule. For the considered objectives under a single disruption constraint or a disruption cost constraint, we propose polynomial-time algorithms and pseudo-polynomial time algorithms, respectively. [ABSTRACT FROM AUTHOR]

The problem of sequencing jobs on a single machine to minimize total cost (earliness and tardiness) is nowadays not just important due to traditional concerns but also due to its importance in the context of Collaborative Networked Organizations and Virtual Enterprises, where precision about promptly responses to customers' requests, along with other important requirements, assume a crucial role. In order to provide a contribution in this direction, in this paper the authors contribute with an applied constructive heuristics that tries to find appropriate solutions for single machine scheduling problems under different processing times and due dates, and without preemption allowed. In this paper, two different approaches for single-machine scheduling problems, based on external and internal performance measures are applied to the problem and a comparative analysis is performed. Computational results are presented for the problem under Just-in-Time and agile conditions on which each job has a due date, and the objective is to minimize the sum of holding costs for jobs completed before their due date and tardiness costs for jobs completed after their due date. Additional computational tests were developed based on different customer and enterprise oriented performance criteria, although preference is given to customer-oriented measures, namely the total number of tardy jobs and the maximum tardiness. [ABSTRACT FROM AUTHOR]

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

The concepts of deteriorating jobs and learning effects have been individually studied in many scheduling problems. However, most studies considering the deteriorating and learning effects ignore the fact that production efficiency can be increased by grouping various parts and products with similar designs and/or production processes. This phenomenon is known as ‘group technology’ in the literature. In this paper, a new group scheduling model with deteriorating and learning effects is proposed, where learning effect depends not only on job position, but also on the position of the corresponding job group; deteriorating effect depends on its starting time of the job. This paper shows that the makespan and the total completion time problems remain polynomial optimal solvable under the proposed model. In addition, a polynomial optimal solution is also presented to minimise the maximum lateness problem under certain agreeable restriction. [ABSTRACT FROM AUTHOR]

In this paper, we study the issue of single-machine rescheduling with linear deteriorating jobs and position-based learning effects simultaneously in response to an unexpected arrival of new jobs. The scheduling efficiency is measured in terms of the makespan, while the cost of disruption is measured in terms of the maximum difference in processing orders of the original jobs before and after disruption. By introducing the effects of deterioration and learning, the job actual processing time is defined by an increasing function of its starting time, meanwhile a decreasing function of its position. Two types of problems are considered. For the first one, the makespan is minimised subject to a limit on the maximum sequence disruption; while in the second one, a linear combination of the makespan and the maximum sequence disruption is minimised. For each problem, the polynomial solvability is demonstrated, and an efficient algorithm is then developed. Finally, extensive computational experiments are conducted to show the efficiency and running behaviours of the proposed algorithms. [ABSTRACT FROM PUBLISHER]

This paper considers single-machine scheduling with learning effect, deteriorating jobs and convex resource dependent processing times, i.e., the processing time of a job is a function of its starting time, its position in a sequence and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately to minimize a cost function containing makespan, total completion (waiting) time, total absolute differences in completion (waiting) times and total resource cost. It is proved that the problem can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

The paper is devoted to some single-machine scheduling problems with variable job processing times. The objectives are to minimize the makespan (i.e., the maximum completion time of all jobs), and to minimize the total completion time. For some special cases, we show that these problems can be solved in polynomial time. For some another special cases of the makespan and the total completion time minimization problems, we prove that an optimal schedule has an V-shape property in terms of processing times. We also propose a heuristic algorithm by utilizing the V-shape property. [ABSTRACT FROM AUTHOR]

In this paper, we explore a single-machine scheduling problem in which the processing time of a job is a linear increasing function of its starting time. The objective is to determine the optimal due date and schedule simultaneously to minimize a cost function that includes the weighted number of tardy jobs and the due date assignment cost. We show that the problem is NP-hard in the ordinary sense. In addition, we propose two dynamic programming algorithms and a fully polynomial-time approximation scheme for the problem. [ABSTRACT FROM AUTHOR]

We consider the scheduling problem in which two agents, each with a set of jobs, compete to perform their respective jobs on a single machine under a group technology (GT) environment. The jobs of agents are classified into groups according to their production similarities in advance, all jobs of the same group are required to be processed contiguously on the machine. A sequence-independent setup time precedes the processing of each group. We propose a polynomial time solution for the problem of minimizing the maximum regular cost of one agent, subject to an upper bound on the maximum regular cost of the second agent. We also show that the problem of minimizing the total completion time of the first agent, subject to an upper bound on the maximum lateness of the second agent is strongly -hard. The case where all groups of the first agent have the same number of jobs is shown to be polynomially solvable. [ABSTRACT FROM AUTHOR]

This paper considers a new scheduling model in which both two-agents and a time-dependent deterioration exist simultaneously. By the time-dependent deterioration, it means that the actual processing time of a job belonging to the two-agents is defined as a non-decreasing linear function of its starting time. Two-agents compete to perform their respective jobs on a common single-machine and each agent has his own criterion to be optimized. The aim is to focus on minimizing total (weighted) earliness cost of one agent, subject to an upper bound on the maximum earliness cost of the other agent. The main contribution of this paper is to propose the optimal properties and present the complexity results for the problems addressed here. [ABSTRACT FROM AUTHOR]

We consider a single-machine common due-window assignment scheduling problem, in which the processing time of a job is a function of its position in a sequence and its resource allocation. 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. For two different processing time functions, we provide a polynomial time algorithm to find the optimal job sequence and resource allocation, respectively. [ABSTRACT FROM AUTHOR]

This paper considers a group scheduling problem with two ordered criteria where both setup times and job-processing times are increasing functions of their starting times. It is assumed that the jobs be classified into several groups and the jobs of the same group have to be processed contiguously. We consider two objectives where the primary criterion is the total weighted completion time and the secondary criterion is the maximum cost. A polynomial time algorithm is presented to solve this bicriterion group scheduling problem with deteriorating setup times and job-processing times. This algorithm can also solve single-machine group scheduling problems with deteriorating setup times and job-processing times in several ordered maximum cost and arbitrary precedence. [ABSTRACT FROM AUTHOR]

Due-window assignment and production scheduling problems are important issues in operations management. In this paper, the problems of common due-window assignment and scheduling of job-dependent deteriorating jobs and multiple deteriorating maintenance activities simultaneously on a single-machine are investigated. We assume that the machine may be subjected to several maintenance activities during the planning horizon. However, due to the restriction of budget of maintenance, the upper bound of the maintenance frequency on the machine is assumed to be known in advance. Moreover, we assume that the duration of each maintenance activity depends on the running time of the machine. Polynomial time algorithms for the all the studied problems are provided, where the objective is to simultaneously minimize the earliness, tardiness, due-window starting time, and due-window size costs. [ABSTRACT FROM AUTHOR]

We study inherent structural properties of a strongly NP-hard problem of scheduling $$n$$ jobs with release times and due dates on a single machine to minimize the number of late jobs. Our study leads to two polynomial-time algorithms. The first algorithm with the time complexity $$O(n^3\log n)$$ solves the problem if during its execution no job with some special property occurs. The second algorithm solves the version of the problem when all jobs have the same length. The time complexity of the latter algorithm is $$O(n^2\log n)$$, which is an improvement over the earlier known algorithm with the time complexity $$O(n^5)$$. [ABSTRACT FROM AUTHOR]

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

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

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

In this article we consider a single-machine scheduling problem with decreasing time-dependent job-processing times. Decreasing time-dependent job-processing times means that its processing time is a non-increasing function of its execution start time. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in the descending order of their normal processing times if they are placed before the job with the smallest normal processing time, but in the ascending order of their normal processing times if placed after it. We prove several other properties of an optimal schedule, and introduce two heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms. [ABSTRACT FROM AUTHOR]

We consider single-machine scheduling problem in which the processing time of a job is a function of its position in a sequence, 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. The problem is modeled as an assignment problem, and thus can be solved in polynomial time. Some extensions of the problem are also shown. [ABSTRACT FROM AUTHOR]

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

Abstract: This paper considers some scheduling problems with deteriorating jobs. The objectives are to minimize the makespan, the total completion time, the total absolute deviation of completion time, the earliness, tardiness, and due date penalty, the sum of earliness penalties subject to no tardy jobs, respectively. We also explore two resource constrained scheduling problems: how to minimize the resource consumption with makespan constraints and how to minimize the makespan with the total resource consumption constraints. Several polynomial time algorithms are proposed to optimally solve the problems with the above objective functions. [Copyright &y& Elsevier]

Abstract: The deteriorating job scheduling problems have received increasing attention recently. However, most researchers assume that the actual job processing time is a linear function of its starting time. In fact, in some situations, the deterioration rate might increase or decrease as time passes. For example, the temperature of the ingot in the rolling machine might drop at a slower pace as the surface cools down. Thus, the drop of the ingot temperature might have a decreasing rate. On the other hand, the time to control a fire might go dramatically as time passes, and the time to cease a fire might have an increasing rate. In this paper, we propose a new deteriorating model where the deterioration rate might be increasing or decreasing as time passes. Under the proposed model, we provide the optimal solutions for some single-machine problems and some flowshop problems. [Copyright &y& Elsevier]

Abstract: In this paper we consider the single-machine scheduling problems with both learning and deterioration effects. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single-machine makespan minimization problem and the sum of the θth power of job completion times minimization problem remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively. [Copyright &y& Elsevier]

In this paper, we presented a scheduling model in which the deteriorating jobs and the setup times are considered at the same time. Under the proposed model, the actual job processing time is a general function of the processing times of jobs already processed and its scheduled position, while the setup time is past-sequence-dependent. We provided the optimal schedules for some single-machine scheduling problems. [ABSTRACT FROM AUTHOR]

Abstract: This paper introduces a new time-dependent learning effect model into a single-machine scheduling problem. The time-dependent learning effect means that the processing time of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. In most related studies, the actual job processing time is assumed to be a function of its scheduled position when the learning effect is considered in the scheduling problem. In this paper, the actual processing time of a job is assumed to be proportionate to the length and position of the already scheduled jobs. It shows that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. It also shows that the shortest processing time (SPT) rule provides the optimum sequence for the addressed problem. [Copyright &y& Elsevier]

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

The concepts of deteriorating jobs and learning effects have been individually studied in many scheduling problems. This note considers a single-machine scheduling problem with deteriorating jobs and learning effects. All of the jobs have a common (but unknown) due date. The objective is to minimize the sum of the weighted earliness, tardiness and due-date penalties. An O(n3) algorithm is proposed to optimally solve the problem with deteriorating jobs and job-dependent learning effect. Besides, an O( n log n) algorithm is provided to solve the problem with deteriorating jobs and job-independent learning effect. [ABSTRACT FROM AUTHOR]

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

This paper considers single-machine scheduling problems with group technology (GT). We consider the case of group setup times and job processing times are a decreasing function of their starting time. We first prove that the makespan minimization problem remains polynomially solvable under the general decreasing linear deterioration. We then prove that the total weighted completion time minimization problem remains polynomially solvable under the proportional decreasing linear deterioration. [ABSTRACT FROM AUTHOR]

This paper considers a single-machine scheduling model with past-sequence-dependent setup times and a general learning effect. It develops a general model with setup times and learning effect considerations where the actual processing time of a job is not only a function of the total actual processing time of the jobs already processed, but also a function of the job’s scheduled position. The paper shows that the single-machine scheduling problems to minimize the makespan and the sum of the kth power of completion times are polynomially solvable under the proposed model. It further shows that the problems to minimize the total weighted completion time and the maximum lateness are polynomially solvable under certain conditions. [ABSTRACT FROM AUTHOR]

We consider a single-machine scheduling problem with deteriorating jobs in which the due dates are determined by the equal slack (SLK) method. By a deteriorating job, we mean that the job’s processing time is an increasing function of its starting time. We model job deterioration as a function that is proportional to a linear function of 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. [ABSTRACT FROM AUTHOR]

In this paper, we consider two single-machine scheduling problems with the effect of deterioration and learning. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. For the following two objective functions, the weighted sum of completion times and the maximum lateness, this paper gives two heuristics according to the corresponding problems without learning effect. This paper also gives the worst-case error bound for the heuristics and provides computational results to evaluate the performance of the heuristics. [ABSTRACT FROM AUTHOR]

The paper deals with the single-machine scheduling problem with a sum-of-processing-time- based learning effect and deteriorating jobs. By the effects of sum-of-processing-time-based 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 the effects of sum-of-processing-time-based learning and deterioration to job processing times, the single-machine makespan minimization problem remains polynomially solvable. [ABSTRACT FROM AUTHOR]

Machine scheduling problems with deteriorating jobs have received increasing attention in recent years, mostly focusing on the linear deterioration models. However, if certain maintenance procedures fail to be completed prior to a prespecified deadline, jobs will require extra time for successful accomplishment in some situations. Therefore, this paper addresses a single-machine problem where the objective is to minimize the makespan under the piecewise linear deterioration model. A branch-and-bound algorithm and two heuristic algorithms are provided to search for the optimal solution and near-optimal solutions, respectively. Computational results are also presented to evaluate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we consider the single-machine scheduling problem with a deteriorating function. By the deteriorating function, we mean that the actual job processing time is a function of jobs already processed. We show that the total completion time minimization problem for a ≥ 1 remains polynomially solvable under the proposed model, where a denotes the deterioration rate. For the case of 0 < a < 1, we show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to normal job processing times. We use the classical smallest processing time first rule as a heuristic algorithm for the case of 0 < a < 1 and analyze its worst-case bound. [ABSTRACT FROM AUTHOR]

Abstract: In this note we consider some single-machine scheduling problems with decreasing time-dependent job processing times. Decreasing time-dependent job processing times means that its processing time is a non-increasing function of its execution start time. We present polynomial solutions for the sum of squared completion times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs, respectively. We also study two resource constrained scheduling problems under the same decreasing time-dependent job processing times model and present algorithms to find their optimal solutions. [Copyright &y& Elsevier]

In many real situations, it is found that if certain maintenance procedures fail to be completed prior to a prespecified deterioration date, then the jobs will require extra time for successful completion. In this paper, a single-machine total completion time problem with step-deteriorating jobs is considered. A branch-and-bound method incorporated with several dominance properties and a lower bound is developed to derive the optimal solution for this problem. In addition, a weight-combination search algorithm is proposed to search for a nearoptimal solution. Computational results indicate that the branch-and-bound algorithm can solve most of the problems with up to 24 jobs in a reasonable amount of time. Moreover, the proposed heuristic algorithm is accurate with mean deviations from the optimum value of less than 0.3%. [ABSTRACT FROM AUTHOR]

This paper considers a single-machine scheduling problem with both deterioration and learning effects. The objectives are to respectively minimize the makespan, the total completion times, the sum of weighted completion times, the sum of the kth power of the job completion times, the maximum lateness, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalties. Several polynomial time algorithms are proposed to optimally solve the problem with the above objectives. [ABSTRACT FROM AUTHOR]