Premium
The effectiveness of the longest delivery time rule for the flow shop delivery time problem
Author(s) -
Kaminsky Philip
Publication year - 2003
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.10054
Subject(s) - computer science , set (abstract data type) , mathematical optimization , flow shop scheduling , routing (electronic design automation) , process (computing) , flow (mathematics) , due date , sequence (biology) , vehicle routing problem , operations research , job shop scheduling , mathematics , computer network , geometry , biology , genetics , programming language , operating system , queue
In the flow shop delivery time problem, a set of jobs has to be processed on m machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize maximum delivery completion time over all the jobs, where the delivery completion time of a job is the sum of its completion time, and the delivery time associated with that job. In this paper, we prove the asymptotic optimality of the Longest Delivery Time algorithm for the static version of this problem, and the Longest Delivery Time among Available Jobs (LDTA) algorithm for the dynamic version of this problem. In addition, we present the result of computational testing of the effectiveness of these algorithms. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003