Sequencing Jobs with Unequal Ready Times to Minimize Mean Flow Time

This paper presents a procedure for sequencing a set of jobs on a single processor (machine) with the objective of minimizing the mean flow time, when the jobs may have unequal ready times. The procedure involves implicit enumeration with the branch and bound technique, coupled with some devices to improve the efficiency of the search. The devices include a sufficient optimality condition, a simple but tight lower bound and rules for tree pruning. The approach has potential applications to other sequencing problems.