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 prop...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.展开更多
基金supported by the National Natural Science Foundation of China (Grant Nos. 51075337, 50705076, 50705077)the Natural Sci-ence Basic Research Plan in Shaanxi Province of China (Grant No. 2009JQ9002)
文摘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.
