An efficient algorithm for a job shop problem Academic Article

abstract

• We study the problem of minimizing makespan in a two-machine job shop with unit processing time operations. An efficient algorithm with respect to a succinct encoding of the problem instances is proposed. The algorithm is an improvement of earlier algorithms proposed for the problem by Brucker [1,2], Hefetz and Adiri [7], and Timkovskiy [15]. The idea behind the algorithm has the potential of extension to job shops with parallel machines. 1995 J.C. Baltzer AG, Science Publishers.

authors

• Sriskandarajah, Chelliah

published proceedings

• Annals of Operations Research

author list (cited authors)

• Kubiak, W., Sethi, S., & Sriskandarajah, C.

complete list of authors

• Kubiak, Wieslaw||Sethi, Suresh||Sriskandarajah, Chelliah

publication date

• January 1, 1995 11:11 AM

publisher

• Springer Nature  Publisher
• Springer Science and Business Media LLC  Publisher

published in

• Annals of Operations Research  Journal

keywords

• Computational Comlexity
• Jobshop
• Polynomial Algorithm
• Scheduling

Digital Object Identifier (DOI)

• 10.1007/bf02099698

start page

• 203

end page

• 216

issue

• 1