AN ADJACENT PAIRWISE APPROACH TO THE MEAN FLOW-TIME SCHEDULING PROBLEM

Abstract

In this paper, sufficient conditions to decide the precedence relation between neighboring two jobs are presented by means of an adjacent pairwise interchage method for minimizing mean flow-time in flow-shop scheduling, On the bases of the sufficient conditions, a computational algorithm is proposed for an optimal or near optimal solution, The mean flow-time by this algorithm puts 90% of the optimal value as an average of over one hundred problems, The algorithm can be executed even by manual calculations within the time proportional to nxm^2, where n and m are the number of jobs and machines respectively.