Permutation flow-shop scheduling problem to optimize a quadratic objective function

ABSTRACT

A flow-shop scheduling model enables appropriate sequencing for each job and for processing on a set of machines in compliance with identical processing orders. The objective is to achieve a feasible schedule for optimizing a given criterion. Permutation is a special setting of the model in which the processing order of the jobs on the machines is identical for each subsequent step of processing. This article addresses the permutation flow-shop scheduling problem to minimize the criterion of total weighted quadratic completion time. With a probability hypothesis, the asymptotic optimality of the weighted shortest processing time schedule under a consistency condition (WSPT-CC) is proven for sufficiently large-scale problems. However, the worst case performance ratio of the WSPT-CC schedule is the square of the number of machines in certain situations. A discrete differential evolution algorithm, where a new crossover method with multiple-point insertion is used to improve the final outcome, is presented to obtain high-quality solutions for moderate-scale problems. A sequence-independent lower bound is designed for pruning in a branch-and-bound algorithm for small-scale problems. A set of random experiments demonstrates the performance of the lower bound and the effectiveness of the proposed algorithms.

KEYWORDS:

• Scheduling
• flow shop
• weighted quadratic completion time
• discrete differential evolution algorithm

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is partially supported by the Forestry Projects in the Central Level Public Welfare Scientific Research Institutes Basic Scientific Research Business Special Funds [grant number CAFYBB2014QA019], National Natural Science Foundation of China [grant numbers 61473073, 61104074, 61203329 and 71201107], Program for Liaoning Excellent Talents in University [grant number LJQ2014028] and Fundamental Research Funds for the Central Universities [grant number N130417006].