Multi-constraint wait-free hybrid running water scheduling modeling method based on idle matrix

Abstract

The invention discloses a multi-constraint wait-free hybrid running water scheduling modeling method based on an idle matrix. The multi-constraint wait-free hybrid running water scheduling modeling method comprises the following steps: firstly, carrying out constraint preprocessing: for a constraint which exhibits processing unit skipping, setting the processing time of a task on a unit as 0, adding a big penalty term when a target function value is calculated for the constraint which exhibits preorders or conversion forbidding, and adding the preparation time after previous task processing time for preparation time which exhibits sequential dependency; secondly, for a stage with a parallel machine, processing by adopting a soft compression regulation method based on a Gantt chart to construct the idle matrix; and finally, on the basis of the idle matrix, constructing a scheduling model according a scheduling target. A wait-free hybrid running water scheduling problem with the complex constraint is converted into a common wait-free running water scheduling problem without the constraint, and the scheduling model is established on the basis of the idle matrix so as to lower the complexity and the solving difficulty of the model.

Description

technical field [0001] The invention belongs to the field of modeling of wait-free mixed pipeline scheduling, and in particular relates to a multi-constraint wait-free mixed pipeline scheduling modeling method based on an idle matrix. Background technique [0002] The no-wait pipeline scheduling problem is an important class of constrained pipeline scheduling problems. It is a typical NP-hard problem and widely exists in process enterprises, such as chemical manufacturing, steel casting, food processing, pharmaceuticals, and plastic manufacturing. The series of processes required are closely linked to prevent decay or contamination. Wait-free pipeline scheduling with parallel machines is also called wait-free hybrid (or flexible) pipeline scheduling. Existing research on wait-free hybrid pipeline scheduling is mainly based on the simplification of the actual process and the assumption of an ideal state. There is no systematic consideration of various constraints in the actu...

AI Technical Summary

Problems solved by technology

Existing research on wait-free hybrid pipeline scheduling is mainly based on the simplification of the actual process and the assumption of an ideal state. There is no systematic consideration of various constraints in the actual process. The main problems are as follows: most of the existing research ignores The preparation time on the processing unit may be considered as a fixed value, but in actual production, this part of the time often has an important impact on the no-wait scheduling problem and the preparation time is also related to the order of production tasks, which needs to be separated during scheduling Consider; most of the existing research assumes that all products go through all stages in sequence and the production sequence can be switched arbitrarily, but for the actual processing process, the production sequence between products prohibits switching from one product to another, or the product has a prior sequence Requirements, or some products may not need to go through certain stages; for multi-stage and complex constraint non-waiting mixed pipeline scheduling problems, the models established by existing methods are complex and difficult to solve

In recent years, the idle time scheduling theory combined with the characteristics of no-wait pipeline scheduling has become an effective method for studying the problem of no-wait pipeline scheduling because it can reduce the computational complexity of no-wait pipeline scheduling, but this method cannot be applied to multi-constraint no-wait Hybrid Pipeline Scheduling

Images