A study on m-machines n-jobs flow shop scheduling problems

This paper deals with one of the most difficult sequencing problems, m-machines n-jobs flow shop scheduling problems. Conventional methods adopted in previous studies include the Monte Carlo method by sampling or the simulation method in which the target or evaluation standard is determined and some machining priority rules are used. In this paper, we employed the Monte Carlo method. Sampled “job execution sequence” is arranged in ascending order of the total elapsed time, and the features obtained from the top “job execution sequence” are reported. In addition, we investigated the relationship between the operating time of each machine on each job and optimum solutions. Specifically, a simple setting with same operating time for each machine was used as a baseline, and then cases where the operating times were changed stepwise were considered to show these changes lead to a proportional rise in difficulty in finding an optimum solution. These results can significantly contribute to a more efficient determination of optimum or quasi-optimum solutions.