Papers by Keyword: Release Dates

Abstract: In this research, a bi-criteria heuristic is proposed to find non-dominated solutions for scheduling unrelated parallel machines with release dates that minimizes makespan andtotal weighted tardiness.

Abstract: This paper studies a two-machine flowshop problem with release dates, rejection and non-availability interval on the first machine. The non-availability interval often origins from equipments maintain or man-power. Usually, in order to pursue maximal profit, some jobs which can be rejected, and in this situation the rejection penalty should be paid. Our objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. For this demonstrated NP-hard in strong sense, we propose a heuristic method and further demonstrate that its worst case performance is 3.

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.

Abstract: This paper focuses on the problem of scheduling n jobs with release dates on a single machine in order to minimize the total completion time. Since the problem has been characterized as strongly NP-hard, two heuristics (HR1 and AEO) were proposed for solving the problem in polynomial time. The heuristics were compared with the best approximation algorithm for this problem to date (Best-alpha). Experimental results show that AEO performed better than the Bestalpha algorithm (selected from the literature) when the number of jobs (n) exceeds 5. This observation should prove useful in the operational dispatch of jobs in industrial production settings as well as the service sector.