《2016 Mixed binary integer programming formulations for the reentrant job shop scheduling problem》.pdf

Computers Operations Research 32 (2005) 1197–1212 /locate/dsw Mixed binary integer programming formulations for the reentrant job shop scheduling problem Jason Chao-Hsien Pana ;∗, Jen-Shiang Chenb a Department of Industrial Management, National Taiwan University of Science and Technology, 43 Keelung Road, Section 4, Taipei 106, Taiwan b Department of Marketing and Logistics Management, National Pingtung Institute of Commerce, 51 Min-Sheng E. Road, Pingtung 900, Taiwan Abstract This paper describes the development of mixed binary integer programming (BIP) formulations for the reentrant job shop scheduling problem. Based on an earlier classical job shop model developed by Manne and improved by Liao and You, this paper presents two extended BIP optimization formulations for the problem under consideration. In order to improve the solution speed of the BIP formulations, two layer division procedures are developed and incorporated in the corresponding models. Results of computational experiments, in which an average performance of these formulations is investigated, are also reported. ? 2003 Elsevier Ltd. All rights reserved. Keywords: Scheduling; Reentrant job shops; Integer programming 1. Introduction The classical job shop scheduling problem is one of the most well-known scheduling problems. It is also known in the literature that the classical job shop scheduling problem is NP-hard [ 1] and thus computationally intractable. However, the assumption that each job visits eac