Papers by Keyword: Total Tardiness

Abstract: We focus on an m-machine re-entrant flowshop scheduling problem with the objective of minimizing total tardiness. In the re-entrant flowshop considered here, routes of all jobs are identical as in ordinary flowshops, but the jobs must be processed multiple times on the machines. We present heuristic algorithms, which are modified from well-known existing algorithms for the general m-machine flowshop problem or newly developed in this paper. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems and results are reported.

Abstract: This paper studies the issue of rescheduling to allow for the unexpected arrival of new jobs, taking into account the effect of the disruptions on a previously planned optimal schedule. We consider the single-machine rescheduling problems with deteriorating jobs. Rescheduling means that a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. The objective is to minimize the total tardiness costs under a limit of the disruptions from the original scheduling. We propose polynomial time algorithms or some dynamic programming algorithms for each problem.

Abstract: To study the identical parallel machine scheduling problem with total tardiness objective, an improved discrete differential evolution DDE_VND is presented. The proposed algorithm hybridizes discrete differential evolution (DDE) with variable neighborhood descent (VND) to enhance its local search ability. Moreover, a constructive heuristic MDD is employed to generate an initial solution in the algorithm to accelerate the convergence of the algorithm. At last, the experimental results based on 50 benchmark instances validate the effectiveness of the DDE_VND algorithm

Abstract: This paper considers the bicriteria scheduling problem of minimizing the total earliness and the total tardiness on a single machine with release dates. In view of the fact that the problem has been characterized as NP-Hard, we propose two approximation algorithms (labeled as ETA1 and ETA2) for solving the problem. The proposed algorithms were compared with the MA heuristic selected from the literature. The two criteria (the total earliness and the total tardiness) were aggregated together into a linear composite objective function (LCOF). The performances of the algorithms were evaluated based on both effectiveness and efficiency. The algorithms were tested on a set of 1200 randomly generated single machine scheduling problems. Experimental results show that both the ETA1 and ETA2 algorithms outperformed (in terms of effectiveness and efficiency) the MA heuristic under all the considered problem sizes. Also, the ETA1 algorithm outperformed the ETA2 algorithm when the number of jobs (n) ranges between 20 and 500.