Authors
Ganggang Niu, Shudong Sun, Pascal Lafon, HongAn Yang,
Title
A decomposition approach to job-shop scheduling problem with discretely controllable processing times
In
Science China Technological Sciences
Volume
54
Issue
5
Pages
1240–1248
Year
2011
Publisher's URL
http://dx.doi.org/10.1007/s11431-010-4249-0
Indexed by
Abstract
Job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is modeled based on the disjunctive graph, and the formulation of JSP-DCPT is presented. A three-step decomposition approach is proposed so that JSP-DCPT can be handled by solving a job-shop scheduling problem (JSP) and a series of discrete time-cost tradeoff problems. To simplify the decomposition approach, the time-cost phase plane is introduced to describe tradeoffs of the discrete time-cost tradeoff problem, and an extreme mode-based set dominant theory is elaborated so that an upper bound is determined to cut discrete time-cost tradeoff problems generated by using the proposed decomposition approach. An extreme mode-based set dominant decomposition algorithm (EMSDDA) is then proposed. Experimental simulations for instance JSPDCPT-FT10, which is designed based on a JSP benchmark FT10, demonstrate the effectiveness of the proposed theory and the decomposition approach. © 2011 Science China Press and Springer-Verlag Berlin Heidelberg.
Affiliations
Offprint