Composite dispatching rules for total weighted tardiness problem

In this thesis, scheduling jobs in various environments of continuous flow manufacturing systems is considered. A number of different jobs, says n, has to go through the system. Each job has a deterministic processing time, due date, release date and weight. A sequence-dependent setup time is incurred between the processing of two consecutive jobs. The objective is the minimization of the sum of the weighted tardinesses.;First, we consider the single machine problem. It is well-known that this problem is unary NP-hard even with no setups. A heuristic which consists of three phases is presented. The first phase consists of a statistical analysis of the problem instance at hand. The second phase takes the form of a priority rule, which is a refinement of the so-called ATC rule. Through extensive experiments rules are developed for determining values for the two look-ahead parameters which make the priority rule work effectively. The third phase, a post processing procedure, refines the sequence obtained in the second phase. A comparison is made between the performance of the proposed priority rule and another rule which has appeared in the literature.;Next, scheduling jobs in a parallel machine environment is considered with setup times independent of the machines. Again, a three phase heuristic is presented. The first and second phases are similar to the first and second phases in the single machine case. In the third phase, a simulated annealing procedure is applied which starts from a seed solution that is obtained in the second phase. The performance of the simulated annealing procedure in the third phase is evaluated for various values of certain job set statistics. The third part of this thesis is the flowshop model in which the machines are set up in series. The proportionate flowshop without setups, in which the processing times of a job at all m machines are equal, is considered. A dispatching rule is suggested and performances are compared with the optimal schedules for various values of job set statistics. A dispatching rule for the proportionate flowshop with setups is also considered.;In the last part of the thesis the Modified ATC dispatching rule is proposed for the single machine problem without setup times. This MATC rule combines the so-called Gamma Date rule, which is a modification of the Earlist Due Date rule, with the ATC rule. It is shown that performances can be improved significantly by applying the MATC rule for the problem which has a special structure. In addition, the worst case structure of the total weighted tardiness problem for the proportional case is investigated, and worst case ratios as functions of job set statistics are found.