CN103105837A - Method used for implementing two-stage mixing optimized batch processing scheduling and based on variable time window - Google Patents

Abstract

The invention provides a method used for implementing two-stage mixing optimized batch processing scheduling and based on a variable time window. According to the method, a decomposition rule of a complex problem is used, an aim of smallest total weighting delaying time is achieved, and two-stage mixing control is implemented. A first stage comprises the steps of based on a multi-rule combined self-adaptive principle, establishing a real-time control platform, adopting a variable time window rolling time domain method to obtain real-time parameters of patch combination and the like. A second stage comprises the steps of based on a flabby method, establishing a flabby linear integer mathematical model, obtaining a solution through a combined engineer of .NET and ILOG CPLEX commercialized software, and obtaining optimized order of batch sequencing. According to the two stages, lot grouping and sequencing for lot grouping in the batch scheduling problem are respectively solved, a multi-entrance property of a batch processor is considered, and according to the variable time window rolling time domain method, a dynamic state real-time scheduling property of machined work piece batches is met. According to the method used for implementing the two-stage mixing optimized batch processing scheduling and based on the variable time window, scheduling accuracy and operating time of a central processing unit (CPU) are considered in a comprehensive mode, real-time optical scheduling of a reentrant next batch processor can be achieved, and the method is beneficial to being popularized and applied in semiconductor field and the like.

Description

Implement the method for two-stage hybrid optimization batch processing scheduling based on the variable time window

Affiliated technical field

The present invention relates to the control method of batch processes scheduling, refer in particular to a kind of method of implementing two-stage hybrid optimization batch processing scheduling based on the variable time window.

Background technology

In semi-conductor chip is made, the batch processors such as boiler tube district scheduling is a typical NP-hard problem in scheduling and control, it is restricting the Whole Performance of semi-conductor manufacturing system, and the rational management control research of carrying out batch processor place is significant to the performance of improving the semiconductor core slice assembly line.

At present, for the batch processes scheduling, there are the precision of scheduling and contradiction working time of dispatching algorithm, can separate extensive NP-hard problem as heuritic approach, can obtain within reasonable time feasible solution, but the precision of separating is difficult to reach requirement sometimes; Linear integer mathematics Accurate Model method for solving because CPU limits working time, can not get optimum solution in the certain limitation time finding the solution extensive NP-hard problem; Semicon industry multiple enters the difficulty that characteristic further increases the batch processes scheduling in addition.

Summary of the invention

For the technical matters that exists in above-mentioned prior art, the invention provides a kind of method of implementing two-stage hybrid optimization batch processing scheduling based on the variable time window, overcome multiple enter the scheduling of semiconductor batch processor production run otherwise precision is low, the deficiency of the long operational time of dispatching algorithm etc., and multiplely enter the problem that characteristic increases the scheduling difficulty.

It is as follows that the present invention specifically solves the technical scheme that its technical matters adopts:

A kind of method of implementing two-stage hybrid optimization batch processing scheduling based on the variable time window, utilize the decomposition method principle of challenge, be that the time-based series model decomposes, resolve into several continuous variable time windows, during based on rolling, domain policy is controlled in real time, stall for time as target take the total weighting of minimum in each time window, implement two stage hybrid optimizations and control.Here " time window " loading time of being defined as adjacent twice idle available batch processor is spaced apart a time window, because appearring in parallel batch processor, do not fix free time, the moment that causes being loaded is not fixed, so the length of time window is not definite value, is namely the variable time window.Phase one sets up based on more rules combination adaptive principle and controls in real time platform, adopt rolling time domain method under the variable time window to obtain processed workpiece and criticize concrete operation process time, operation excess time, due date, the priority that product is criticized and the real-time parameters such as batch combination of criticizing principle formation according to certain group form data basd link and receive subordinate phase; Subordinate phase is based on relaxation method, set up the linear integer mathematical model of laxization, find the solution by .NET and ILOG CPLEX commercial software associating engine, realize obtaining the optimization order of batch sequence, and with result feedback to the phase one so that the phase one load priority the highest batch to available batch processor of free time.How two stages organizes in batch scheduling problem batch and how with batch sequence of institute group if solving respectively, multiple to enter character considered, by the rolling time domain method under the variable time window, satisfies the dynamic Real-Time Scheduling characteristic that processed workpiece is criticized.

Phase one can obtain processed workpiece and criticize concrete operation process time, operation excess time, due date, the priority that product is criticized and the real-time parameters such as batch combination of criticizing principle formation according to certain group, form database, offer subordinate phase and find the solution, the concrete steps that its circulation is carried out:

Step 1, upper available batch processor of a free time just has been loaded complete, initialization time window, the phase one strategy brings into operation;

Step 2 is obtained the batch processor running status that is scheduled, and obtains workpiece quantity and affiliated product family information in the batch processor anterior bumper that is scheduled;

Step 3, a batch processor free time is available when having, produce trigger event, this free time, available batch processor was in wait, the real-time control platform of phase one is organized batch immediately, exports current processed workpiece and criticizes concrete operation process time, operation excess time, due date, the priority that product is criticized, and building database, offer subordinate phase; When subordinate phase feeds back to the phase one with the highest the criticizing of all to be processed batch of medium priorities, the phase one will criticize in the idle available batch processor that is loaded into wait, and a time window scheduling is complete;

Step 4, end condition are that the general plan production run is complete dispatching cycle, if satisfy end condition, stop immediately, otherwise iteration turn back to step 1.

Set up the linear integer mathematical model of laxization and find the solution concrete steps:

Step 1 is set up being connected of outside programming language .NET and ILOG CPLEX commercial software, and externally programming language is introduced ILOG.CPLEX.dll and ILOG.Concert.dll two spaces;

Step 2 is stalled for time as under target in the total weighting of minimum, sets up based on lax linear mixed-integer mathematical model:

Target

$\mathrm{\ΣT}=\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{w}_i*\max [(C_i-d_i),0]$

Constraint condition

$C_i=t+(\mathrm{Positionarray}\left(i\right)-1)\×\stackrel{\‾}{P_h}+P_i+{\mathrm{RP}}_i;\∀i\∈\{\mathrm{1,2},\·\·\·,h\}$

$\stackrel{\‾}{P_h}=\left(\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{P}_i\right)/h$

${\mathrm{RP}}_i=\underset{q=r_i+1}{\overset{S_j}{\mathrm{\Σ}}}{P}_{\mathrm{qj}};$ $\∀i\∈\{\mathrm{1,2},\·\·\·,h\};$ $\∀j\∈\{\mathrm{1,2},\·\·\·,J\}$

Positionarray(i)∈{1,2,…,h};

Ifi≠lthen?Positionarray(i)≠Positionarray(l);

Here t represents that current scheduling constantly; H is illustrated in the total lot amount numbers to be scheduled such as reentry batch processor place; w _iRepresent i batch weight; C _iRepresent the deadline that i criticizes; d _iRepresent i batch delivery date; RP _iRepresent that i criticizes the residue process time in the batch processing back; P _iRepresent i batch of process time in batch processor; S _jThe technique total step number that represents j product; r _iBe illustrated in the technique number of product j in the reentry batch processor; P _qjRepresent j product the required process time of q technique; J is illustrated in different product quantity in the batch processor of can reentrying;

Be illustrated in the total lot amounts to be scheduled such as reentry batch processor place and count the average activity time of h; The majorizing sequence position is one-dimension array, can be expressed as: Positionarray (1), and Positionarray (2) ..., Positionarray (i) ..., Positionarray (h);

Step 3 is fetched data from database read, i.e. the database that provides of rolling lower phase one of time domain method under variable time window;

Step 4 is found the solution by .NET and ILOG CPLEX commercial software associating engine, obtains the optimal scheduling sequence, and operation result feeds back to the phase one.

The invention has the beneficial effects as follows, the algorithm that adopts the variable time window to implement the two-stage hybrid optimization decomposes extensive NP-hard problem, criticize how to organize in scheduling problem and criticize and how institute's group is criticized to sort and find the solution by two stages the simplification problem that reaches respectively, by the rolling time domain method under the variable time window, satisfy the dynamic Real-Time Scheduling characteristic that processed workpiece is criticized, consider the CPU working time of precision and the dispatching algorithm of scheduling, realize the real-time optimal scheduling of the multiple batch processor that enters to reentry down.

Description of drawings

Below in conjunction with drawings and Examples, patent of the present invention is further described.

Fig. 1 is the present invention batch processor dummy model figure that reentries;

In figure, 1. input, 2. product family one, and 3. impact damper two, and 4. the equipment group three, 5. output, 6. the equipment group four, and 7. impact damper three, the 8. j of product family, 9. the equipment group two, 10. impact damper one, 11. equipment group one;

Fig. 2 the present invention is based on the variable time window to implement process flow diagram under variable time window in the method for two-stage hybrid optimization batch processing scheduling;

Process flow diagram when Fig. 3 is the rolling of phase one of the present invention under domain policy;

Fig. 4 is that example of the present invention is implemented dummy model figure;

Fig. 5 is the operation result figure of example implementation model of the present invention.

Embodiment

Referring to Fig. 1, have the batch processing typical virtual model of reentry characteristic, mainly comprise four equipment groups: equipment group 1, equipment group 29, equipment group 34 and equipment group 46, wherein equipment group 1 is equipment group 29 upstream equipment groups; Equipment group 29 is batch processors of studying, is multimachine parallel (in the dotted line frame, not marking in figure); Equipment group 34 and equipment group 46 are equipment group 29 upstream device groups.Product stream is to being to enter from equipment group 1, from 46 outputs of equipment group.Equipment group 1 has impact damper 1 between equipment group 29 and equipment group 34, between equipment group 29 and equipment group 34, impact damper 23 is arranged, and between equipment group 29 and equipment group 4, impact damper 37 is arranged.Workpiece in impact damper 1 is from the hyperpycnal inflow of equipment group 1 and equipment group 29, and the part flow in impact damper 1 is to equipment group 29.Workpiece in impact damper 23 is from equipment group 29, and the part flow in impact damper 23 is to equipment group 34.Workpiece in impact damper 37 is from equipment group 29, and the part flow in impact damper 37 is to equipment group 46.Require in addition: the parallel equipment group of each in equipment group 29 can only be processed a kind of product family, as product family 1 ..., the j8 of product family criticizes when processed when certain product, and this batch do not allow to stop or increasing workpiece, namely seizes not allow; Parallel equipment group 29 not can with the time free time available; Equipment group 29 hunger can not occur.

Referring to Fig. 2 and Fig. 3, the specific implementation process of the method that batch processing is dispatched based on variable time window enforcement two-stage hybrid optimization provided by the present invention is as follows:

Phase one sets up based on more rules combination adaptive principle and controls in real time platform, and subordinate phase is set up the linearization integer mathematical model of laxization based on relaxation method, finds the solution by .NET and ILOG CPLEX commercial software associating engine.

Rolling time domain method under the variable time window obtains processed workpiece from the phase one and criticizes concrete operation process time, operation excess time, due date, the priority level that product is criticized and the real-time parameters such as batch combination of criticizing principle formation according to certain group, building database, offer subordinate phase and find the solution, the concrete steps that its circulation is carried out:

Step 1, upper available batch processor of a free time just has been loaded complete, initialization time window, the phase one strategy brings into operation;

Step 2 is obtained the batch processor running status that is scheduled, and obtains workpiece quantity and affiliated product family information in the batch processor anterior bumper that is scheduled;

Step 3, a batch processor free time is available when having, produce trigger event, this free time, available batch processor was in wait, the real-time control platform of phase one is organized batch immediately, export current processed workpiece criticize have operation process time, operation excess time, due date, the real-time parameters such as priority level that product is criticized, and building database, offer subordinate phase; (subordinate phase is extremely of short duration working time when subordinate phase feeds back to the phase one with the highest the criticizing of all to be processed batch of medium priorities, generally below 2 minutes, criticizing a sequence need 98 seconds as subordinate phase to there being 16) time, phase one will criticize in the idle available batch processor that is loaded into wait, and a time window scheduling is complete;

Step 4, end condition are that the general plan production run is complete dispatching cycle, if satisfy end condition, stop immediately, otherwise iteration turn back to step 1.

Set up the linear integer mathematical model of laxization and find the solution concrete steps:

Step 1 is set up being connected of outside programming language .NET and ILOG CPLEX commercial software, and externally programming language is introduced ILOG.CPLEX.dll and ILOG.Concert.dll two spaces;

Step 2 is stalled for time as under target in the total weighting of minimum, sets up based on lax linear mixed-integer mathematical model:

Target

$\mathrm{\ΣT}=\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{w}_i*\max [(C_i-d_i),0]$

Constraint condition

$C_i=t+(\mathrm{Positionarray}\left(i\right)-1)\×\stackrel{\‾}{P_h}+P_i+{\mathrm{RP}}_i;\∀i\∈\{\mathrm{1,2},\·\·\·,h\}$

$\stackrel{\‾}{P_h}=\left(\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{P}_i\right)/h$

${\mathrm{RP}}_i=\underset{q=r_i+1}{\overset{S_j}{\mathrm{\Σ}}}{P}_{\mathrm{qj}};$ $\∀i\∈\{\mathrm{1,2},\·\·\·,h\};$ $\∀j\∈\{\mathrm{1,2},\·\·\·,J\}$

Positionarray(i)∈{1,2,…,h};

Ifi≠lthen?Positionarray(i)≠Positionarray(l);

Here t represents that current scheduling constantly; H is illustrated in the total lot amount numbers to be scheduled such as reentry batch processor place; w _iRepresent i batch weight; C _iRepresent the deadline that i criticizes; d _iRepresent i batch delivery date; RP _iRepresent that i criticizes the residue process time in the batch processing back; P _iRepresent i batch of process time in batch processor; S _jThe technique total step number that represents j product; r _iBe illustrated in the technique number of product j in the reentry batch processor; P _qjRepresent j product the required process time of q technique; J is illustrated in different product quantity in the batch processor of can reentrying;

Be illustrated in the total lot amounts to be scheduled such as reentry batch processor place and count the average activity time of h; The majorizing sequence position is one-dimension array, can be expressed as: Positionarray (1), and Positionarray (2) ..., Positionarray (i) ..., Positionarray (h);

Step 3 is fetched data from database read, i.e. the database that provides of rolling lower phase one of time domain method under variable time window;

Step 4 is found the solution by .NET and ILOG CPLEX commercial software associating engine, obtains the optimal scheduling sequence, and operation result feeds back to the phase one.

Provide a kind of virtual reentried batch processor example model referring to accompanying drawing 4, have 8 kinds of dissimilar equipment group zones: PAN, AAN, SAN, ASI, MRH, DIK, GON and LPC, wherein DIK equipment group zone is research object, following view is the stretch-out view of top view.Fig. 5 is based on the method that the variable time window is implemented two-stage hybrid optimization batch processing scheduling, is having 10 to wait to dispatch concrete total run time, desired value and the optimal scheduling sequencing information of criticizing under ILOG CPLEX based on lax linear integer model under certain time window.

Claims (3)

1. implement based on the variable time window method that the batch processing of two-stage hybrid optimization is dispatched for one kind, it is characterized in that, comprise that implementing two stage hybrid optimizations controls: the phase one sets up and controls in real time platform, subordinate phase is set up the linear integer mathematical model of laxization, adopt the rolling time domain method circulation under the variable time window to carry out Real-Time Scheduling control, wherein: the phase one sets up based on more rules combination adaptive principle and controls in real time platform, provide subordinate phase required related data, subordinate phase is based on relaxation method, set up the linear integer mathematical model of laxization, to obtain processed workpiece the phase one criticizes and has operation process time, operation excess time, due date, the priority level that product is criticized and batch combination real-time parameter of criticizing principle formation according to certain group, setting up engine by .NET and ILOG CPLEX commercial software finds the solution, realize obtaining the optimization order of batch sequence, the highest batch of operation result medium priority is fed back to the phase one, exist side by side and namely be loaded in idle available batch processor, execution moves in circles, until end condition satisfies.

2. the method for implementing two-stage hybrid optimization batch processing scheduling based on the variable time window according to claim 1, is characterized in that, the concrete steps that the rolling time domain method circulation under described employing variable time window is carried out are as follows:

Step 1, upper available batch processor of a free time just has been loaded complete, initialization time window, the phase one strategy brings into operation;

Step 2 is obtained the batch processor running status that is scheduled, and obtains workpiece quantity and affiliated product family in the batch processor anterior bumper that is scheduled;

Step 3, a batch processor free time is available when having, produce trigger event, this free time, available batch processor was in wait, the real-time control platform of phase one is organized batch immediately, exports current processed workpiece and criticizes concrete operation process time, operation excess time, due date, the priority level real-time parameter that product is criticized, and building database, offer subordinate phase; When subordinate phase feeds back to the phase one with the highest the criticizing of all to be processed batch of medium priorities, the phase one will criticize in the idle available batch processor that is loaded into wait, and a time window scheduling is complete;

Step 4, end condition are that the general plan production run is complete dispatching cycle, if satisfy end condition, stop immediately, otherwise iteration turn back to step 1.

3. the method for implementing two-stage hybrid optimization batch processing scheduling based on the variable time window according to claim 1, is characterized in that, the linear integer mathematical model of described laxization of subordinate phase foundation and the concrete steps of finding the solution are as follows:

Step 1 is set up being connected of outside programming language .NET and ILOG CPLEX commercial software, and externally programming language is introduced ILOG.CPLEX.dll and ILOG.Concert.dll two spaces;

Step 2 is stalled for time as under target in the total weighting of minimum, sets up based on lax linear mixed-integer mathematical model:

Target

$\mathrm{\ΣT}=\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{w}_i*\max [(C_i-d_i),0]$

Constraint condition

$C_i=t+(\mathrm{Positionarray}\left(i\right)-1)\×\stackrel{\‾}{P_h}+P_i+{\mathrm{RP}}_i;$ $\∀i\∈\{\mathrm{1,2},\·\·\·,h\}$

$\stackrel{\‾}{P_h}=\left(\underset{i=1}{\overset{h}{\mathrm{\Σ}}}{P}_i\right)/h$

${\mathrm{RP}}_i=\underset{q=r_i+1}{\overset{S_j}{\mathrm{\Σ}}}{P}_{\mathrm{qj}};$ $\∀i\∈\{\mathrm{1,2},\·\·\·,h\};$ $\∀j\∈\{\mathrm{1,2},\·\·\·,J\}$

Positionarray(i)∈{1,2,…,h};

Ifi≠lthen?Positionarray(i)≠Positionarray(l);

Here t represents that current scheduling constantly; H is illustrated in the total lot amount numbers to be scheduled such as reentry batch processor place; w _iRepresent i batch weight; C _iRepresent the deadline that i criticizes; d _iRepresent i batch delivery date; RP _iRepresent that i criticizes the residue process time in the batch processing back; P _iRepresent i batch of process time in batch processor; S _jThe technique total step number that represents j product; r _iBe illustrated in the technique number of product j in the reentry batch processor; P _qjRepresent j product the required process time of q technique; J is illustrated in different product quantity in the batch processor of can reentrying; Be illustrated in the total lot amounts to be scheduled such as reentry batch processor place and count the average activity time of h; The majorizing sequence position is one-dimension array, can be expressed as: Positionarray (1), and Positionarray (2) ..., Positionarray (i) ..., Positionarray (h);

Step 3 is fetched data from database read, i.e. the database that provides of rolling lower phase one of time domain method under variable time window;

Step 4 is found the solution by .NET and ILOG CPLEX commercial software associating engine, obtains the optimal scheduling sequence, and operation result feeds back to the phase one.

Images