Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine

This paper treats the problem of minimizing the total weighted flow cost plus job-processing cost in a single machine sequencing problem for jobs having processing costs which are linear functions of processing times. The optimal job sequence and processing times are obtainable from the solution of an associated problem of optimal row and column selection in a symmetric matrix. Some sufficient conditions for expediting certain jobs are proved. In order to handle cases in which these conditions fail to complete the solution to the problem a heuristic algorithm with a provable performance bound is developed. The heuristic solutions are compared with optimal solutions obtained by branch and bound in numerous randomly generated problems and are found to be optimal in most cases.