The job-shop problem and immediate selection

The job-shop problem and immediate selection

0.00 Avg rating0 Votes
Article ID: iaor1995549
Country: Switzerland
Volume: 50
Issue: 1
Start Page Number: 73
End Page Number: 114
Publication Date: Sep 1994
Journal: Annals of Operations Research
Authors: , ,
Abstract:

The job-shop problem is one of the most difficult NP-hard scheduling problems. A 10×10-problem published in 1963 has been solved only recently by Carlier and Pinson using a branch and bound method. Other branch and bound algorithms have been developed recently. The efficiency of all these branch and bound methods relies on the concept of immediate selection which allows to introduce order relations on the set I of all operations to be processed on the same machine before branching. The authors present new algorithms for immediate selection. Among them are (a) an O(max{nlogn,f})-algorithm for fixing all disjunctions induced by cliques; (b) an O(n2)-algorithm based on concepts which are different from those used by Carlier and Pinson. Here, n is the number of operations in I and f is the number of induced order relations.

Reviews

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