On-line Scheduling with a Monotonous Subsequence Constraint

In this paper, we study a new on-line scheduling problem that each server has to process a monotonous request subsequence. The customer requests are released over-list, and the operator has to decide whether or not to accept the current request and arrange it to a server immediately. The goal of this paper is to find a strategy which accepts the maximal requests. When the number of servers k is less than that of the request types m, we give several lower bounds for this problem. Also, we present the optimal strategy for \( k=1 \) and \( k=2 \) respectively.