An On-line Approach for Emergency Relief Scheduling Problem under Uncertainty

In order to reduce losses, Relief Transfer Center needs to make a trade-off between the urgency degree and the size of demands. Assuming the losses of unsatisfied relief demands have a positive relationship with delayed time, this paper first get an optimal offline strategy under the known demand sequences and point out that the time complexity is O(n²); secondly, under the unknown demand sequences, we use a on-line approach to get the competitive ratio of strateunsatisfied relief demandsgy FIFO and MQF; at last, aim to the characteristics of this problem, we give a on-line strategy with competitive ratio (2M)/(M+m).