Two-machine flow-shop scheduling to minimize total late work

Two-machine flow-shop scheduling to minimize total late work

0.00 Avg rating0 Votes
Article ID: iaor2007657
Country: United Kingdom
Volume: 38
Issue: 4
Start Page Number: 501
End Page Number: 509
Publication Date: Jun 2006
Journal: Engineering Optimization
Authors: , ,
Keywords: production, manufacturing industries, programming: branch and bound
Abstract:

This article considers a two-machine flow-shop scheduling problem of minimizing total late work. Unlike tardiness, which is based upon the difference between the job completion time and the due date, the late work of a job is defined as the amount of work not completed by its due date. This article first shows that the problem remains non-deterministic polynomial time (NP) hard even if all jobs share a common due date. A lower bound and a dominance property are developed to design branch-and-bound algorithms. Computational experiments are conducted to assess the performance of the proposed algorithms. Numerical results demonstrate that the lower bound and dominance rule can help to reduce the computational efforts required by exploring the enumeration tree. The average deviation between the solution found by tabu search and the proposed lower bound is less than 3%, suggesting that the proposed lower bound is close to the optimal solution.

Reviews

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