Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach

A. Bagheria, M. Zandiehb
Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran, Received 23 May 2010; revised 13 January 2011; Accepted 22 February 2011. Available online 21 April 2011.


In scheduling problems, taking the sequence-dependent setup times into account is one of the important issues that have recently been considered by researchers in the production scheduling field. In this paper, we consider flexible job-shop scheduling problem (FJSP) with sequence-dependent setup times to minimize makespan and mean tardiness. The FJSP consists of two sub-problems from which the first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on all machines. To solve this problem, a variable neighborhood search (VNS) algorithm based on integrated approach is proposed. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed the search process. To search the solution space, the internal loop used two main search engines, i.e. shake and local search procedures. In addition, neighborhood structures related to the sequencing problem and the assignment problem were employed to generate neighboring solutions. To evaluate the performance of the proposed algorithm, 20 test problems in different sizes are randomly generated. Consequently, computational results and comparisons validate the quality of the proposed approach.

Go to Journal

Check Also

Thermal conductivity of a Jurkat cell measured by a transient laser point heating method - Advances in Engineering

Thermal conductivity of a Jurkat cell measured by a transient laser point heating method