A penalty-shift-insertion-based algorithm to minimize total flow time in no-wait flow shops

作者：Laha Dipak; Gupta Jatinder N D^*; Sapkal Sagar U

来源：Journal of the Operational Research Society, 2014, 65(10): 1611-1624.

DOI：10.1057/jors.2013.118

• scheduling
• no-wait flow shop
• total flow time
• Vogel%26apos
• s penalty-based heuristic
• forward shift heuristic
• insertion heuristic

This paper proposes a penalty-shift-insertion (PSI)-based algorithm for the no-wait flow shop scheduling problem to minimize total flow time. In the first phase, a penalty-based heuristic, derived from Vogel%26apos;s approximation method used for the classic transportation problem is used to generate an initial schedule. In the second phase, a known solution is improved using a forward shift heuristic. Then the third phase improves this solution using a job-pair and a single-job insertion heuristic. Results of the computational experiments with a large number of randomly generated problem instances show that the proposed PSI algorithm is relatively more effective and efficient in minimizing total flow time in a no-wait flow shop than the state-of-the-art procedures. Statistical significance of better results obtained by the proposed algorithm is also reported.

• 出版日期2014-10