Single-machine scheduling with uncertain durations for optimizing service logistics with one truck

A single-machine scheduling problem is studied for the optimization of the service logistics with one truck and uncertain (interval) times needed for the truck to supply products from the warehouse to n supermarkets S1, S2,..., Sn. We propose to use the following additional criterion: to find the permutation Pk with the maximal relative perimeter of the optimality box. We investigate properties of the optimality box and develop efficient algorithms for constructing the permutation Pk having the largest relative perimeter of the optimality box. Computational results with small, moderate and large benchmark instances showed that such permutation Pk is close to the factual optimal permutation Pm for the main criterion (the permutation Pm is determined when all factual times ti become known)