Flow-line scheduling problem with controllable processing times

In this paper we address the simultaneous scheduling and optimal-processing-times selection problem in a multi-product deterministic flow line operated under a cyclic scheduling approach. The selection of processing times plays an important role in achieving the desired production rate with the least possible operating cost. We first formulate the important subproblem of optimal-processing-times selection for different objectives, when the sequence of jobs is fixed, and then develop an efficient solution procedure for it. The fast solution of the fixed sequence problem is necessary for the development of efficient approximate solution procedures for the simultaneous scheduling and optimal-processing-times problem. A computational study on the effectiveness of the proposed solution procedure is presented. For the solution of the simultaneous scheduling and optimal-processing-times problem we suggest an iterative solution procedure, and report our computational experience with this procedure. For the solution of large problems we present a genetic algorithm. The effectiveness of the algorithm is demonstrated through computational results and by evaluating the performance of the obtained solutions against lower bounds that we developed for the problem.