Sequencing to minimize the maximum renewal cumulative cost

This paper considers the problem of sequencing n independent tasks, each of which is associated with a cost. The objective is to minimize the maximum cumulative cost incurred during the execution of the set of tasks. After a task has been executed, the cumulative cost is equal to the larger of zero and the previously cumulated cost plus the cost of the task. This problem is strongly NP-hard. An algorithm is developed that solves this problem in O(logn) time when two types of tasks are involved.