Improving earliest starting times in machine scine scheduling problem

Abstract

For every activity v _i of a job-shop scheduling problem an interval [f _i s _i] is given, meaning that v, cannot start earlier thanf _i and must be completed not later than s _i, in any optimal schedule. The use of such intervals often accelerates existing algorithms. We demonstrate how such dates can be improved by an iteration procedure. Here, the values for the v _i result from the optimal solution of a one machine problem where operations may be interrupted. The influence of these [f _i s _i] intervals on some f _i is discussed even for the case where there is no order relation between v _i and v _j

Keywords:

• Job-shop scheduling
• Earliest starting times