Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness,weighted tardiness and weighted flowtime of jobs

In many manufacturing systems, jobs that are completed early are held as finished-goods inventory until their due-dates, and hence we incur earliness costs. Similarly, jobs that are completed after their due-dates incur penalty. The objective in such situations would, therefore, be to meet the due-dates of the respective jobs as closely as possible, and consequently minimize the sum of earliness and tardiness of jobs because earliness and tardiness of jobs greatly influence the performance of a schedule with respect to cost. In addition, a job incurs holding cost from the time of its arrival until its completion. Most studies on scheduling in such manufacturing systems assume unit earliness cost, unit tardiness cost and unit holding cost of a job. However, in reality such an assumption need not always hold and it is quite possible that there exist different costs of earliness, tardiness and holding for different jobs. In addition, most studies on job-shop scheduling assume that jobs are independent and that no assembly operations exist. The current study addresses the problem of scheduling in dynamic assembly job-shops (i.e. shops that manufacture multi-level jobs) with the consideration of jobs having different earliness, tardiness and holding costs. An attempt is made in this paper to present dispatching rules by incorporating the relative costs of earliness, tardiness and holding of jobs in the form of scalar weights. In the first phase of the study, relative costs (or weights for) earliness and tardiness of jobs are considered, and the dispatching rules are presented in order to minimize the sum of weighted earliness and weighted tardiness of jobs. In the second phase of the study, the objective considered is the minimization of the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs, and the dispatching rules are presented by incorporating the relative costs of earliness, tardiness and flowtime of jobs. Simulation studies have been conducted separately for both phases of the current study, the performance of the scheduling rules have been observed independently, and the results of the simulation study have been reported. The proposed rules are found to be effective in minimizing the mean and maximum values of the measures of performance.     

Single-machine scheduling with a common due window

We study several single-machine non-preemptive scheduling problems to minimize the sum of weighted earliness–tardiness, weighted number of early and tardy jobs, common due window location, and flowtime penalties. We allow the due window location to be either a decision variable or a given parameter. We assume that the due window location has a tolerance and the window size is a given parameter. We further make the assumption that the ratios of the job processing times to the earliness–tardiness weights are agreeable for the first problem. We propose pseudo-polynomial dynamic programming algorithms to optimally solve the problems. We also provide polynomial time algorithms for several special cases.Scope and purpose The widespread use of Just-In-Time philosophy in manufacturing to eliminate inventories leads to a new class of scheduling problems in which the earliness and/or number of early jobs are penalized as well as the tardiness and/or tardy jobs. In this type of environments, the jobs are sometimes associated with a period of time within which they incur no penalty since the customers will generally allow a time interval for the delivery of the products. This time period is called a due window. There are a variety of applications with due windows in factory automation, production maintenance, and so on. In this paper, we consider the common due window problems to minimize the weighted earliness–tardiness, weighted number of early–tardy jobs and weighted flowtime on a single machine. The main contributions of this paper are identifying the computational complexity of the problems, developing dynamic programming algorithms to optimally solve them, and providing efficient and exact polynomial algorithms for the special cases.     

Dispatching in flowshops with bottleneck machines

This paper addresses the problem of dispatching in flowshops with bottleneck machines. The presence of bottleneck machines results in the restricted throughput in flowshops. The objective is to develop dispatching rules for scheduling by taking into account the presence of bottleneck machines. The measures of performance are the minimization of total flowtime of jobs, the minimization of the sum of earliness and tardiness of jobs, and the minimization of total tardiness of jobs, considered separately. Many existing conventional dispatching rules and the proposed dispatching rules have been extensively investigated for their performance by generating a large number of problems of various sizes and bottleneck conditions. The results of the experimental investigation show that the proposed dispatching rules emerge to be superior to the conventional dispatching rules.     

Heuristics for scheduling in flowshops and flowline-based manufacturing cells to minimize the sum of weighted flowtime and weighted tardiness of jobs

The problem of scheduling in two different types of flowshops (all jobs available at time zero, different job availability times known a priori) and in flowline-based manufacturing cells is considered with the objective of minimizing the sum of weighted flowtime and weighted tardiness of jobs. First, heuristic preference relations are developed by the consideration of lower bounds on the completion times, operation due-dates, and weights for holding and tardiness of jobs. A heuristic algorithm for scheduling is then proposed by making use of the heuristic preference relations. Two more heuristic algorithms are developed by implementing an improvement scheme to enhance the quality of the solution given by the first heuristic algorithm. The proposed and the existing heuristics are evaluated with respect to the three problem classes under consideration by solving a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that all three proposed heuristics perform better than the existing heuristics in giving a solution of superior quality and that the first proposed heuristic yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the existing heuristics, and also the effectiveness of heuristics based on simulated annealing. The results are discussed in detail.     

Scheduling rules for dynamic shops that manufacture multi-level jobs

The problem of scheduling in dynamic conventional jobshops has been extensively investigated over many years. However, the problem of scheduling in assembly jobshops (i.e. shops that manufacture multi-level jobs with components and subassemblies) has been relatively less investigated in spite of the fact that assembly jobshops are frequently encountered in real life. A survey of literature on dynamic assembly jobshop scheduling has revealed that the TWKR-RRP rule is the best one for minimizing the mean flowtime and staging delay, and the job due-date (JDD) rule is the best for minimizing the mean tardiness of jobs. However, the objectives of minimizing the maximum flowtime (and maximum staging delay) and standard deviation of flowtime (and standard deviation of staging delay) are as important as the minimization of mean flowtime and mean staging delay. Likewise, the objectives of minimizing the maximum tardiness and standard deviation of tardiness are also as important as the minimization of mean tardiness. The reason is that the maximum and standard deviation values of a performance measure indicate the worst-case performance of a dispatching rule. The present study seeks to develop efficient dispatching rules to minimize the maximum and standard deviation of flowtime and staging delay, and the maximum and the standard deviation of conditional tardiness of jobs. The dispatching rules are based on the computation of the earliest completion time of a job and consequently determining the latest finish time of operations on components/subassemblies of a job. An extensive simulation-based investigation of the performance evaluation of the existing dispatching rules and the proposed dispatching rules has been carried out by randomly generating jobs with different structures and different shop utilization levels. It has been found from the simulation study that the proposed rules are quite effective in minimizing the maximum and standard deviation of flowtime and staging delay, and the maximum conditional tardiness and standard deviation of conditional tardiness.     

Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule.     

A note: Common due date assignment for a single machine scheduling with the rate-modifying activity

In this paper we study the single machine common due date assignment and scheduling problem with the possibility to perform a rate-modifying activity (RMA) for changing the processing times of the jobs following this activity. The objective is to minimize the total weighted sum of earliness, tardiness and due date costs. Placing the RMA to some position in the schedule can decrease the objective function value. Several properties of the problem are considered which in some cases can reduce the complexity of the solution algorithm.     

Soft Due Window Assignment and Scheduling on Parallel Machines

We study problems of scheduling jobs on identical parallel machines, in which a due window has to be assigned to each job. If a job is completed within its due window, then it incurs no scheduling cost. Otherwise, it incurs earliness or tardiness cost. Two due window models are considered. In both models, the due window size is a decision variable common for all jobs. In the first model, called a constant due window, the due window starting time is a decision variable common for all jobs, and in the second, called a slack due window, the due window starting time is equal to the job processing time plus a decision variable common for all jobs. The objective is to find a job schedule as well as the size and location(s) of the due window(s) such that a weighted maximum or sum of costs associated with job earliness, job tardiness, and due window size is minimized. We establish the properties of optimal solutions of these minmax and minsum problems. For a constant due window model, we prove that the minmax problem with arbitrary weights and the minsum problem with equal weights are polynomially equivalent to the classical parallel machine scheduling problem to minimize the makespan. We further show that the problems for a constant due window model and slack due window model with the same objective function are reversible in the sense that their optimal solutions are mirror images of each other. These results imply O(n) and O(n log n) time algorithms for the considered problems when m=1.     

Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance

We consider the problem of scheduling a set of jobs on a single machine against a common and restrictive due date. In particular, we are interested in the problem of minimizing the weighted sum of maximum earliness and maximum tardiness costs. This kind of objective function is related to the just-in-time environment where penalties, such as storage cost and additional charges for late delivery, should be avoided. First we present a mixed integer linear model for the problem without availability constraints and we prove that this model can be reduced to a polynomial-time model. Secondly, we suppose that the machine undergoes a periodic preventive maintenance. We present then a second mixed integer linear model to solve the problem to optimality. Although the latter problem can be solved to optimality for small instances, we show that the problem reduces to the one-dimensional bin packing problem. Computational results show that the proposed algorithm best fit decreasing performs well.     

An exact approach to early/tardy scheduling with release dates

In this paper, we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into weighted earliness and weighted tardiness subproblems. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.     

Single CNC machine scheduling with controllable processing times to minimize total weighted tardiness

Advanced manufacturing technologies, such as CNC machines, require significant investments, but also offer new capabilities to the manufacturers. One of the important capabilities of a CNC machine is the controllable processing times. By using this capability, the due date requirements of customers can be satisfied much more effectively. Processing times of the jobs on a CNC machine can be easily controlled via machining conditions such that they can be increased or decreased at the expense of tooling cost. Since scheduling decisions are very sensitive to the processing times, we solve the process planning and scheduling problems simultaneously. In this study, we consider the problem of scheduling a set of jobs on a single CNC machine to minimize the sum of total weighted tardiness, tooling and machining costs. We formulated the joint problem, which is NP-hard since the total weighted tardiness problem (with fixed processing times) is strongly NP-hard alone, as a nonlinear mixed integer program. We proposed a DP-based heuristic to solve the problem for a given sequence and designed a local search algorithm that uses it as a base heuristic.     

Group scheduling and job-dependent due window assignment based on a common flow allowance

We study a single-machine group scheduling and job-dependent due window assignment problem in which each job is assigned an individual due window based on a common flow allowance. In the group technology environment, the jobs are divided into groups in advance according to their processing similarities and all the jobs of the same group are processed consecutively in order to improve production efficiency. A sequence-independent machine setup time precedes the processing of the first job of each group. A job completed earlier (later) than its due window will incur an earliness (tardiness) penalty. Our goal is to find the optimal sequence for both the groups and jobs, together with the optimal due window assignment, to minimize the total cost that comprises the earliness and tardiness penalties, and the due window starting time and due window size costs. We give an O(n log n)time algorithm to solve this problem.     

An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem

We present an optimal solution procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. In this problem, we assume the constrained renewable resources are limited to very expensive equipments and machines that are used in other projects and are not available in all periods of time of a project. In other words, for each resource, there is a dictated ready date as well as a due date such that no resource can be available before its ready date but the resources are permitted to be used after their due dates by paying penalty cost depending on the resource type. We also assume that only one unit of each resource type is available and no activity needs more than it for execution. The objective is to determine a schedule with minimal total weighted resource tardiness penalty costs. For this purpose, we present a branch-and-bound algorithm in which the branching scheme starts from a graph representing a set of conjunctions (the classical finish-start precedence constraints) and disjunctions (introduced by the resource constraints). In the search tree, each node is branched to two child nodes based on the two opposite directions of each undirected arc of disjunctions. Selection sequence of undirected arcs in the search tree affects the performance of the algorithm. Hence, we developed different rules for this issue and compare the performance of the algorithm under these rules using a randomly generated benchmark problem set.     

Computer simulation of due-date setting in multi-machine job shops

The due-date setting and operations scheduling problem is addressed in an unbalanced, multi-machine random job shop. The focus of the study is to demonstrate the feasibility of setting reliable static due-dates through operation flow time analysis. Response-surface mapping methodology via regression analysis is employed to model operation flow time characteristics, which are shown to be non-linear and dispatching rule dependent. Discussion points out the advantages and practicality of using static job information as opposed to dynamic shop information in setting due-dates. Simulation results and statistical analyses show the viability of setting due-dates that are tight, reliable, and consistent, using this methodology. A unique characteristic of the proposed method is that it shows simultaneous reductions in variability of manufacturing lead times, tardiness, proportion of tardy jobs, and maximum tardiness without resorting to looser due-dates.     

Minimizing weighted earliness–tardiness on parallel machines using hybrid metaheuristics

We consider the problem of scheduling a set of jobs on a set of identical parallel machines where the objective is to minimize the total weighted earliness and tardiness penalties with respect to a common due date. We propose a hybrid heuristic algorithm for constructing good solutions, combining priority rules for assigning jobs to machines and a local search with exact procedures for solving the one-machine subproblems. These solutions are then used in two metaheuristic frameworks, Path Relinking and Scatter Search, to obtain high quality solutions for the problem.The algorithms are tested on a large number of test instances to assess the efficiency of the proposed strategies.The results show that our algorithms consistently outperform the best reported results for this problem.     

Minimizing total earliness and tardiness on a single machine using a hybrid heuristic

This paper focuses on scheduling jobs with different processing times and distinct due dates on a single machine with no inserted idle time as to minimize the sum of total earliness and tardiness. This scheduling problem is a very important and frequent industrial problem that is common to most just-in-time production environments. This NP hard scheduling problem is herein solved using a hybrid heuristic which combines local search heuristics (dispatching rules, hill climbing and simulated annealing) and an evolutionary algorithm based on genetic algorithms. The heuristic involves low and high, relay and teamwork hybridization. Computational results reflect the sizeable solution quality improvement induced by hybridization, and assess the impact of each type of hybridization on the efficiency of the hybrid heuristic.     

Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem

In this paper, we consider the single machine scheduling problem with weighted quadratic tardiness costs. Several efficient dispatching rules are proposed. These include existing heuristics for the linear problem, as well as procedures suitably adapted to the quadratic objective function. Also, both forward and backward scheduling procedures are considered.The computational results show that the heuristics that specifically take into account the quadratic objective significantly outperform their linear counterparts. Also, the backward scheduling approach proves to be superior, and the difference in performance is even more noticeable for the harder instances.The best of the backward scheduling heuristics is both quite efficient and effective. Indeed, this procedure can quickly generate a schedule even for large instances. Also, its relative deviation from the optimum is usually rather low, and it performs adequately even for the more difficult instances.     

用模拟退火法解任务的加工时间为模糊区间数的单机提前/拖期调度问题

研究了单机作业下任务的加工时间为模糊区间数的提前／拖期调度问题。     

A BI-criterion approach to minimizing inventory costs on a single machine when early shipments are forbidden

In this paper, the concept of job earliness as a measure of inventory costs for single machine scheduling is introduced. The justification of earliness as a cost is presented. It is pointed out that the Japanese have long recognized earliness as a cost. The addition of earliness greatly complicated finding an optimum solution, since reducing earliness may require the insertion of machine idle time. Another measure commonly used to represent inventory cost is flowtime. In this paper, a combination of earliness and flowtime is used to represent total inventory costs. Some preliminary results are presented illustrating the complexity of solving this problem.     

Scheduling job classes on uniform machines

We study a scheduling problem with job classes on parallel uniform machines. All the jobs of a given class share a common due-date. General, non-decreasing and class-dependent earliness and tardiness cost functions are assumed. Two objectives are considered: (i) minmax, where the scheduler is required to minimize the maximum earliness/tardiness cost among all the jobs and (ii) minmax-minsum, where the scheduler minimizes the sum of the maximum earliness/tardiness cost in all job classes. The problem is easily shown to be NP-hard, and we focus here on the introduction of simple heuristics. We introduce LPT (Largest Processing Time first)-based heuristics for the allocation of jobs to machines within each class, followed by a solution of an appropriate non-linear program, which produces for this job allocation an optimal schedule of the classes. We also propose a lower bound, based on balancing the load on the machines. Our numerical tests indicate that the heuristics result in very small optimality gaps.