The complexity of a single batch processing machine in the case of two arrival times and a 2-approximation algorithm

The complexity of a single batch processing machine in the case of two arrival times and a 2-approximation algorithm

0.00 Avg rating0 Votes
Article ID: iaor20021189
Country: China
Volume: 26
Issue: 4
Start Page Number: 19
End Page Number: 21
Publication Date: Oct 2000
Journal: Journal of Qufu Normal University
Authors: , , ,
Keywords: programming: dynamic
Abstract:

In this paper, the problem of minimizing the total completion time on a single batch processing machine in the case of two arrival times is discussed. Its NP-Completeness is proved and a polynomial approximation algorithm with performance ratio of 2 is given.

Reviews

Required fields are marked *. Your email address will not be published.