A decomposition method for jobshop scheduling

A decomposition method for jobshop scheduling

0.00 Avg rating0 Votes
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: , ,
Keywords: production, engineering
Abstract:

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.]

Reviews

Required fields are marked *. Your email address will not be published.