The algorithm design idea proposed in this paper is to optimize the scheduling results without increasing the time complexity of the comprehensive scheduling algorithm. Through analysis, it is found that the quasi critical path scheduling method pays too much attention to the vertical scheduling of processes in the process tree and ignores the parallel scheduling of horizontal processes [7], resulting in unsatisfactory scheduling results. Therefore, based on the scheduling results of quasi critical path algorithm, this paper proposes to adjust the scheduling sequence of adjacent processes and parallel processes on each process, so as to adjust the scheduling of subsequent processes, so as to find a better solution. The algorithm framework is as follows:
1. Set the number of device required during product processing as N and the total number of processing processes on each device as nd;
2. Calculate the processing path length of each process node in the product processing process tree;
3. Use the quasi critical path strategy to generate the product scheduling scheme and add it to the set of alternative product scheduling schemes;
4. For i = 1 to N;
5. For j = 1 to Nd-1;
6. Based on the product scheduling scheme generated by the proposed critical path strategy, use the adjacent process exchange strategy of the same device to select the exchange process and exchange the scheduling sequence;
7. Use the same device process exchange adjustment strategy to adjust the processes affected by the exchange process in step 6 to generate a new product scheduling scheme;
8. Add the scheduling scheme obtained in step 7 to the set of alternative product scheduling schemes;
9. Next i;
10. Next j;
11.In the set of alternative product scheduling schemes, the optimal product scheduling scheme selection strategy is used to select the optimal scheduling scheme.
12.Generate product scheduling Gantt chart.
Next, the adjacent process exchange strategy of the same device, the adjacent process exchange adjustment strategy of the same device and the optimal product scheduling scheme selection strategy are introduced in detail.
3.1Analysis and design of the adjacent process exchange strategy of the same device
Suppose there are 20 processes in the process tree, as shown in Fig. 1,namely A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S and T. These processes are scheduled according to the quasi-critical path algorithm, and the result is, the sequence of processes on M1 is: A, B, C, D, E, F and G; The process sequence on M2 is: H, I, J, K and L; The process sequence of M3 is: M, N, O, P, Q, R, S and T. As shown in Fig. 1, the processes on each processing device are arranged in a queue in order, and the final order is A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, Q, R, S and T. Start from the first step A, look for adjacent procedures on the same device one by one, and judge whether they can be exchanged. Obviously, process G and process H, process L and process M, these two adjacent processes cannot be exchanged because they do not belong to the same processing device. The remaining adjacent processes need to be further determined whether the processing sequence can be interchangeable. The method is: to judge whether there is A serial relationship between the current process and the tight post-process in the process queue. If there is, it cannot be exchanged; otherwise, the processing order of the tight post-process in the process A and the same device will be exchanged.
As shown in Fig. 3, processes A and B on the same processing device M3 processes, in its processing device process C has already on the M3 is processed, in addition, the process is A process before processing technology in the tree close to process A ', is processed on device M2, tight in the working procedure in process B tree before working procedure for process B ', the device is processed on the M1, the two can exchange, exchange process is divided into three kinds of circumstances:
(1) When the end time of process A 'and B' are less than the end time of process C, the beginning time of process A is the end time of process C, and the beginning time of process B is the end time of process A. When process A and process B are exchanged, only the start time of process A is set as the start time of process B, and the end time of process B is set as the start time of process A.
(2) When the end time of process B 'is greater than that of process C, the beginning time of process A is the end time of process C, and the beginning time of process B is the end time of process A. When process A and process B are exchanged, only the start time of process B' is set as the start time of process B, and the end time of process B is set as the start time of process A.
(3) When the end time of process A 'is greater than the end time of process C, the beginning time of process A' is the end time of process A ', and the beginning time of process B is the end time of process A. When process A and Process B are exchanged, only the start time of process B 'is set as the start time of process B, and the end time of process B is set as the start time of process A.
To sum up, in order to realize the exchange between process A and process B, the starting time of process B can be determined first, and then the starting time of process A can be determined.
The specific steps of adjacent process interchange strategy of the same device are as follows:
Step 1: Determine whether process A and its tight rear process B in queue Q belong to A processing device; if yes, go to 2; otherwise, go to 5.
Step 2: Determine whether there is A serial relationship between process A and process B; if yes, go to 5; otherwise, go to 3.
Step 3: Adjust process B to be before process A, and the processing start time is the maximum value of the end time of the pre-tightening process of original process A and the end time of the pre-tightening process of process B in the process tree.
Step 4: Adjust the process A to be before the process B, and take the maximum value of the end time of the process B and the end time of the process A in the process tree.
Step 5: end.
3.2 Analysis and design of the adjacent process exchange adjustment strategy of the same device
For a process, its current optimal processing time should be the maximum value of the end time of the process before tightening the device and the end time of the process before tightening the process in its process tree.
The algorithm steps are as follows:
Step 1: Judge whether there is a pre-tightening process in the process tree. If there is no turning to 2, if there is turning to 4;
Step 2: Set the finishing time of the pre-tight work in the process tree of this process to 0 and turn it to 4;
Step 3: Judge whether there is a pre-tightening process of the device in this process. If it does not turn to 4, if it does turn to 5;
Step 4: Set the finishing time of the process before tightening the device in this process to 0 and turn it to 5;
Step 5: Take the maximum value of the end time of the process before tightening the device of the process and the end time of the process before tightening in the process tree of the process as the processing time of the current process;
Step 6:end.
3.3 Optimal product scheduling scheme selection strategy analysis and design
The algorithm steps are as follows:
Step 1: Judge whether the current scheduling set is empty. If it is, go to 4; if not, go to 2.
Step 2: Select the scheme with the minimum total product processing time in the set as the selection scheme;
Step 3: Return the selected object scheme;
Step 4:end.
3.4 Implementation steps of the proposed algorithm
The algorithm steps are as follows:
Step 1: The quasi-critical path strategy is adopted to determine the scheduling sequence of each process in the product processing tree.
Step 2: Use the first adaptation strategy to determine the scheduling time of each process in the product processing process tree, and form the original scheduling plan D.
Step 3: Set up a total of M processing device.
Step 4: i = 1.
Step 5: Judge that I < = M, if true, go to 6, if not, go to 8.
Step 6: Put all the processes on the ith device in the original scheduling scheme into queue Q according to the processing order.
Step 7: i++, go to 5.
Step 8: Determine whether there is only one process in queue Q, instead of going to 9, go to 17.
Step 9: Queue A from queue Q.
Step 10: Start the adjacent processes interchange strategy process A, If the interchange occurs, go to 11; otherwise go to 12.
Step 11: Start the adjacent process interchange strategy and go to 12.
Step 12: Add the resulting new product scheduling solution to the product scheduling solution set, and go to 8.
Step 13: Calculate the total processing time of each product scheduling scheme in the product scheduling scheme set respectively.
Step 14: Select the final scheduling scheme of the product according to the optimal scheduling scheme selection policy.
Step 15: Output the gantt chart of scheduling results.
3.5 Complexity analysis of the proposed algorithm
Let all the cross points in the product processing tree whose input degree is greater than 1 be K, that is, the number of subtrees be K, the total number of work order be N, and the number of device be M. Based on literature [7], that the critical path algorithm complexity to O{Max[(n(n-m)/(2m)),(nn)/(16m)]}.
In this paper, the adjacent process interchange strategy of the same device is designed. The average number of processes involved in this algorithm is N /2, and the operational complexity of the algorithm for the interchange of processes is O(1), and the time complexity of this strategy algorithm is O(n/2). The adjacent process exchange adjustment strategy of the same device is designed, which involves at most N-1 processes. The operation algorithm complexity of the adjustment of process processing time is O(1), and the time complexity of this strategy algorithm is O(n-1).
Due to the quasi-critical path strategy, the adjacent process interchange strategy and the adjustment strategy for the interchange between adjacent processes are serial operations, so the time complexity of the algorithm in this paper is the same as that of the algorithm in literature [7], which is O{Max[(n(n-m)/(2m)), (nn)/(16m)]}.