A Decomposition Algorithm for Bicriteria Job-Shop Scheduling Problem with Discretely Controllable Processing Times

The job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is formulated. A decomposition strategy is applied so that the problem could be solved by solving a classical JSP problem and a series of discrete time-cost tradeoff problems. Based on the partition of the solution space and the appliance of the set dominance, an extreme mode based set dominant decomposition (EMSDD) algorithm is proposed. It is proved that the solution space of JSP-DCPT could be reduced by restricting the makespan to an upper bound value which is derived by EMSDD.