Search

In this paper, the single-machine scheduling problems with deteriorating effects and a machine maintenance are studied. In this circumstance, the deterioration rates of the jobs during the machining process are the same which reduces the production efficiency. The actual processing time of the job is a linearly increasing function of the starting time. In this process, the machine only performs a maintenance activity, and the maintenance time is a fixed value. After the maintenance work is completed, the machine will be restored to the initial state, and the deterioration of the job will be start again. The goal is to determine the optimal schedule in order to minimise the maximum completion time (i.e. the makespan) and the sum of job completion times. We prove that both problems are polynomial time solvable, and we also provide the corresponding algorithms. [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]

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]

Two-agent scheduling has gained a lot of research attention recently. Two competing agents who have their own objective functions have to perform their respective set of jobs on one or more shared machines. This study considers a two-agent single-machine earliness and tardiness scheduling problem where jobs have distinct due dates and unforced idleness in between any two consecutive jobs is allowed. The objective is to minimize the total earliness and tardiness of jobs from one agent given that the maximum earliness–tardiness of jobs from the other agent cannot exceed an upper bound. In other words, each job from the second agent has a hard due window, whereas each job from the first agent will incur a penalty if completed either before or after its due date. Two mathematical models of the problem are presented, and several necessary optimality conditions are derived. By exploiting the established dominance properties, heuristic algorithms are developed for the problem. Finally, computational experiments are conducted to assess the models and heuristic procedures. [ABSTRACT FROM AUTHOR]

There is a situation found in many manufacturing systems, such as steel rolling mills, fire fighting or single-server cycle-queues, where a job that is processed later consumes more time than that same job when processed earlier. The research finds that machine maintenance can improve the worsening of processing conditions. After maintenance activity, the machine will be restored. The maintenance duration is a positive and non-decreasing differentiable convex function of the total processing times of the jobs between maintenance activities. Motivated by this observation, the makespan and the total completion time minimization problems in the scheduling of jobs with non-decreasing rates of job processing time on a single machine are considered in this article. It is shown that both the makespan and the total completion time minimization problems are NP-hard in the strong sense when the number of maintenance activities is arbitrary, while the makespan minimization problem is NP-hard in the ordinary sense when the number of maintenance activities is fixed. If the deterioration rates of the jobs are identical and the maintenance duration is a linear function of the total processing times of the jobs between maintenance activities, then this article shows that the group balance principle is satisfied for the makespan minimization problem. Furthermore, two polynomial-time algorithms are presented for solving the makespan problem and the total completion time problem under identical deterioration rates, 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]

Scheduling with learning effects has been widely studied. However, there has been little work done on multi-agent scheduling with learning effects. This article investigates a two-agent single-machine scheduling problem with learning effects via an objective function which minimises the weighted completion time of all the jobs subject to a constraint that one agent makespan cannot exceed a prescribed upper bound. This article develops a branch-and-bound algorithm along with three simulated-annealing (SA) algorithms searching for an optimal and near-optimal solution. The computational results show that all the average error percentages of combined SA algorithms are less than 0.076%. [ABSTRACT FROM PUBLISHER]

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]

This article introduces a general single-machine setup times scheduling model with learning effect and deteriorating jobs simultaneously which is a generalisation of some existing models in the literature. 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). By the effects of learning and deterioration, we mean that the actual processing time of a job depends not only on the starting time of the job but also on its scheduled position. The article shows that the problems to minimise the makespan, sum of the kth power of completion times, total lateness and sum of earliness penalties (with common due date) are polynomially solvable under the proposed model. It further shows that the problems to minimise total weighted completion time, maximum lateness, maximum tardiness, total tardiness and total weighted earliness penalties (with common due date) are polynomially solvable under certain conditions. [ABSTRACT FROM AUTHOR]

In most studies, the learning effect model applied in a scheduling problem assumes that the actual processing time of a job is a function of its scheduled position or the sum of the normal processing times of the jobs already scheduled. In this article, we introduce a learning effect model and a past-sequence-dependent (psd) setup time into a single machine group scheduling problem. The actual processing time of a job in each group is a function of the sum of the normal processing times of the jobs already scheduled and the position of the corresponding job group in the sequence. It shows that the addressed problem remains polynomially solvable for the objectives: minimisation of the makespan and the total completion time. It also shows that the smallest processing time rule provides the optimal jobs sequence in each group and the optimal group sequence for the addressed problem, respectively. [ABSTRACT FROM AUTHOR]

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]

We study a problem of scheduling a maintenance activity on a single machine. Following several recent papers, the maintenance is assumed to be deteriorating, that is, delaying the maintenance increases the time required to perform it. The following objective functions are considered: makespan, flowtime, maximum lateness, total earliness, tardiness and due-date cost, and number of tardy jobs. We introduce polynomial time solutions for all these problems. [ABSTRACT FROM AUTHOR]

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]

In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we study a single-machine scheduling problem with the cyclic process of an aging effect. This phenomenon appears in many realistic production processes. Thus, it is important to consider the phenomenon in scheduling problems. We analyse the single-machine makespan scheduling problem with two different aging effect models and provide a polynomial time algorithm to solve the problem. [ABSTRACT FROM AUTHOR]

Several research studies have confirmed that people and organizations become better at their tasks as the tasks are repeated. The effect of this learning phenomenon on classical scheduling problems has been studied recently. One of the single-machine scheduling problems which seems to become nontrivial when learning effects are introduced is that of minimizing the number of tardy jobs. in this note, we study the special case where all jobs share a common due-date. We show that even when the learning process is assumed to be general and job-dependent. the problem remains polynomially solvable. [ABSTRACT FROM AUTHOR]