Extending the single machine-based relaxation scheme for the job shop scheduling problem

Journal Article

Gharbi, Anis . 2010

• رابط المنشور على الويب: Extending the single machine-based relaxation scheme for the job shop scheduling problem
• الوسوم: Lower Bounds, Release Dates, Delivery Times, Delayed Precedence Constraints
• المجلة \ الصحيفة: Electronic Notes in Discrete Mathematics
• رقم الإصدار السنوي: 36
• الصفحات: 1057–1064

مستخلص المنشور

The contribution of this paper to the job shop related literature is twofold. First, we provide an efficient way forf solving the job shop scheduling problem with release dates, delivery times and delayed precedence constraints. It is shown that the latter problem is equivalent to a classical job shop with precedence constraints. Second, an effective extension of the standard single machine-based relaxation scheme is derived. Preliminary computational results conducted on a set of benchmark instances show that effective multiple machine-based lower bounds can be computed within reasonable CPU time.