Heuristics for minimisation of completion time variance in a flow shop

This paper provides two heuristics to obtain a near-optimal solution for a n-job, m-machine now shop scheduling problem. Non regular performance measure of completion time variance (CTV) is the objective. The heuristic also yields the desired common due date or delivery date. The first heuristic primarily aims at determining the first job using lower bounds of makespan. The remaining jobs are then fixed by insertion and exchange. The second heuristic revolves around reducing the problem into (m-1) two machine auxiliary problems. For each auxiliary problem, with the starting seed in V-shape, the best sequence is found by insertion and exchange. Both heuristics yield < 5% deviation from global optimal (by complete enumeration for problems with < 8 jobs). For larger sized problems, the heuristics yield satisfactory near-optimal solutions. The heuristics will be applicable in industries to arrive at the common due date, minimising CTV between due date and completion time.