Article ID: | iaor19921325 |
Country: | Japan |
Volume: | 27 |
Issue: | 5 |
Start Page Number: | 607 |
End Page Number: | 613 |
Publication Date: | May 1991 |
Journal: | Transactions of the Society of Instrument and Control Engineers |
Authors: | Nishikawa Yoshikazu, Tamaki Hisashi, Maki Atsuto |
Keywords: | production, engineering |
In recent years, as the diversification of consumers’ demand and the progress of production technology result in a wider variety of products, the necessity of effective scheduling is increasing. This paper is concerned with a jobshop scheduling problem (JSP), which has a wide area of practical applications. First, the degree of difficulty (DOD) of JSP is defined, and then quantified according to several characteristics of the problem: number of machines, number of operations, processing times of operations, precedence relations among operations, and their mutual relations. Second, an algorithm of decomposition referring to DOD is proposed for dealing with large-scale problems. In our algorithm, the original JSP is decomposed into several partial problems are arranged in a time-sequence and are almost even in DOD. These partial problems are then solved sequentially by the branch-and-bound method. Finally, the effectiveness of the proposed method is affirmed by means of several computational experiments. [In Japanese.]