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. W...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(n^2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.展开更多
文摘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(n^2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.