Article ID: | iaor20081706 |
Country: | China |
Volume: | 21 |
Issue: | 1 |
Start Page Number: | 103 |
End Page Number: | 109 |
Publication Date: | Mar 2006 |
Journal: | Chinese Quarterly Journal of Mathematics |
Authors: | Li Wenhua |
In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.