Scheduling's Algorithm Of Nonstandard Job-Shop Based On Filtered Beam Search And Its Application

To meet the various demands of the market, the production mode of most manufacturing enterprises has been changed from the volume-produce mode to the multi-varieties and small-batch mode. Especially, the machining mode of the manufacturing enterprise whose production is good-sized and consists of some constructional parts can only select the make-to-order mode but not the merchandise on hand with inventory existing mode, because that the latter mode can tie up abundance capital. The purpose of this dissertation is to develop a practical algorithm on nonstandard job-shop scheduling problem with constructional relationship among its parts under the make-to-order mode, and develop a production scheduling system oriented to big device equilibrium to fulfill the practical demands of Harbin Electric Machinery Limited Company.Firstly, the whole scheme of the production scheduling system oriented to big device equilibrium is systematically analyzed and designed in this dissertation. Secondly, based on the analysis of the relationship between the processing tasks, a hybrid algorithm combined the filtered beam search algorithm with the local search algorithm is proposed. The main idea of this hybrid algorithm is: at first, all candidates in task collection is lined according to a dispatching rule (Earliest Due Date, EDD), then this linear queue is divided into some tiers under a criterion that partial order is not allowed to exist in the every tier, many feasible sequences is generated by constructing a neighborhood of a initial sequence in every tier, the allocation of the resources over time is conducted to perform every feasible task sequence, and a set of approximate optimal scheduling schemes is achieved as the precondition of the next tier's disposal in meeting multiple scheduling objectives to obtain the global near-optimal schedule which makes these program run tier by tier until the last task is completed. Thirdly, for most of the real world decision problems involved the multiple and conflicting objectives that should be tackled while respecting the various constraints, it is impossible in multi-objective problems to get some one optimized solution to satisfy all the objectives. Therefore, it is important to simplify the system of the performance indices according to the scheduling...