Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion

Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion

0.00 Avg rating0 Votes
Article ID: iaor20072848
Country: Netherlands
Volume: 105
Issue: 2
Start Page Number: 407
End Page Number: 424
Publication Date: Jan 2007
Journal: International Journal of Production Economics
Authors: , , ,
Keywords: optimization: simulated annealing, heuristics: tabu search
Abstract:

In the paper, the flow-shop scheduling problem with parallel machines at each stage (machine center) is studied. For each job its release and due date as well as a processing time for its each operation are given. The scheduling criterion consists of three parts: the total weighted earliness, the total weighted tardiness and the total weighted waiting time. The criterion takes into account the costs of storing semi-manufactured products in the course of production and ready-made products as well as penalties for not meeting the deadlines stated in the conditions of the contract with customer. To solve the problem, three constructive algorithms and three metaheuristics (based on Tabu Search and Simulated Annealing techniques) are developed and experimentally analyzed. All the proposed algorithms operate on the notion of so-called operation processing order, i.e. the order of operations on each machine. We show that the problem of schedule construction on the base of a given operation processing order can be reduced to the linear programming task. We also propose some approximation algorithm for schedule construction and show the conditions of its optimality.

Reviews

Required fields are marked *. Your email address will not be published.