Effective heuristics for the single machine sequencing problem with ready times

In this paper we consider the single machine sequencing problem with different ready times in which the objective is to minimize the mean completion time (or mean flow time, or the sum of completion times, or the sum of flow times). We propose some heuristics for the problem and give conditions under which the heuristics give optimal sequences. A MILP formulation and a branch and bound procedure are used to generate optimal solutions for comparison with those which the heuristics generate. Computational testing shows that the heuristics yield excellent sequences in a very short time. Full computational details and results are given in this paper.