Study on constraint scheduling algorithm for job shop problems with multiple constraint machines

Authors: Zuo, Yan¹; Gu, Hanyu¹; Xi, Yugeng¹

Source: International Journal of Production Research, Volume 46, Number 17, September 2008 , pp. 4785-4801(17)

Purchase options

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$42.75 plus tax Refund Policy

More about this publication?

More like this?

In this: publication
By this: publisher
In this Subject: Materials & Manufacturing
By this author: Zuo, Yan ; Gu, Hanyu ; Xi, Yugeng

Content Key:

- Free

- New

- Open Access

- Subscribed

- Free Trial

Abstract:

This paper focuses on a job-shop scheduling problem with multiple constraint machines (JSPMC). A constraint scheduling method for the JSPMC is proposed. It divides the machines in the shop into constraint and non-constraint machines based on a new identification method, and formulates a reduced problem only for constraint machines while replacing the operations of non-constraint machines with time lags. The constraint machines are scheduled explicitly by solving the reduced problem with an efficient heuristic, while the non-constraint machines are scheduled by the earliest operation due date (EODD) dispatching rule. Extensive computational results indicate that the proposed constraint scheduling algorithm can obtain a better trade-off between solution quality and computation time compared with various versions of the shifting bottleneck (SB) methods for the JSPMC.

Keywords: Scheduling; Job shop; Constraint machine; Shifting bottle neck

Document Type: Research article

DOI: 10.1080/00207540701324143

Affiliations: 1: Department of Automation, School of Electronics, Shanghai 200240, China