Browse Prior Art Database

Statistical Branch and Bound Algorithm

IP.com Disclosure Number: IPCOM000073807D
Original Publication Date: 1971-Feb-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 71K

Publishing Venue

IBM

Related People

Topp, DW: AUTHOR [+2]

Abstract

This program is to determine an optimum solution to the sequencing of a series of jobs, such as manufacturing different kinds of items in a general purpose facility as with manufacturing different grades of paper with a paper machine.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Statistical Branch and Bound Algorithm

This program is to determine an optimum solution to the sequencing of a series of jobs, such as manufacturing different kinds of items in a general purpose facility as with manufacturing different grades of paper with a paper machine.

The sequencing problem is the task of determining the rank or order of material passing over or through a facility to yield an optimum solution, i.e., which produces the least set up changes on the facility without reducing production rates or scrap losses.

The problem may also be stated: minimize function F where:

(Image Omitted)

In step 10 the changeover matrix from Table II is read as data from punched cards. In step 11, the above data is printed for the user. In step 12 all the above data is stored on disk. In step 13 an index counter is set equal to 1 to count a chosen number of random sequences of connections between matrix points on Table II. Step 14 generates a random sequence of connections between the points within the range of the number of points (jobs) indicated by a parameter card for comparison with the counter. In step 15 the random sequence values are evaluated. In the case of costs of job sequences the costs for the instant random sequence of papercutting jobs are summed and the results are stored on disk. In step 16 the counter is increased and in step 17 the counter is tested to determine whether the number of sequences specified in the parameter card have been generated. Until they have, the process loops back to step 14 until the test is met and step 19 calculates the mean value X of the above generated sequences. Step 20 calculates the standard error of X. Step 21 sets the number- of-jobs counter at I.

Starting in step 22 the Branch and Bound algorithm of J. D. C. Little in Operations Research and the Design of Information Systems, J. F. Pierce, Ed., Badger Printing Corp., Appleton, Wisconsin 1967 is used.

In step 22 the RowRE subroutine determines the smallest element in each row, and the RowRD subroutine reduces each row of the changeover matrix in Table II by the smallest element in each row. In step 23 the COLRE subroutine determines the smallest element in each column after the matrix has been row reduced, and the COLRD subroutine reduces each row of the changeover matrix by the smallest element in each column. In step 24 the THETA subroutine evaluates the...