We investigate online scheduling with commitment on parallel identical machines. Our objective is the maximization of the total system load. The online restriction requires us to decide immediately at the submission of a job whether we accept or reject it while the commitment restriction forces us to complete every accepted job on time. For every job, there is a minimum amount of scheduling flexibility defined by the system parameter ε such that for the deadline d, the processing time p, and the release date r, the relation d≥(1+ε)∙p + r holds. Any algorithm for this problem must address job acceptance and job allocation.

First we focus on problems with a job flexibility that does not exceed the processing time of the job, that is, we consider ε≤1. In this we use a combination of two approaches for job acceptance: a lazy approach for small values of ε and greedy acceptance for values of ε that are closer to 1. For job allocation, we give priority to the most loaded machine if we have a choice and generate a simple semi-active schedule. We show that the combination of these two algorithms achieves an optimal competitive ratio in the P2 environment for the whole range 0<ε≤1. For the general Pm environment, this combination of algorithms is optimal only for parts of this range, specifically when ε is either close to 0 or close to 1.

For problems with a large job flexibility, we show that we cannot guarantee the greedy competitive ratio for large values of ε and for more than 2 machines. Even for two machines, the allocation problem turns out to be more defficult than for problems with little flexibility.