TREE SEARCH-BASED SCHEDULING METHOD AND ELECTRONIC APPARATUS USING THE SAME

• US 20190146463A1
• Filed: 02/05/2018
• Published: 05/16/2019
• Est. Priority Date: 11/16/2017
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Hsieh, Tsung-Jung, Chang, Sen-Chia, Hsu, Yao-Chung, Kuo, Che-Ming, Chung, I-Hsuan
• Granted Patent: US 10,642,257 B2
• Time in Patent Office: Days
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/32252 Scheduling production, machining, job shop
• CPC Class Codes: G05B 2219/32266 Priority orders
• CPC Class Codes: G05B 2219/32269 Decision, of job release, select job to be launched next in shop
• CPC Class Codes: G05B 2219/32306 Rules to make scheduling decisions
• CPC Class Codes: G05B 2219/34379 Job management
• CPC Class Codes: G05B 2219/45031 Manufacturing semiconductor wafers
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 50/04 Manufacturing
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y02P 90/30 Computing systems specially adapted for manufacturing

Abstract

A tree search-based scheduling method and an electronic apparatus are provided. In the method, multiple order lists are received and a schedule is initialized, wherein each order list includes multiple production operations. In each order list, a first production operation which has not been joined into the schedule yet is selected, such that multiple prior operations are selected. An execution priority of the prior operations is calculated according to multiple dispatching rules, and multiple candidate operations are selected from the prior operations according to the execution priority. Afterwards, the candidate operations are listed as a next operation of the schedule respectively, and a scheduling simulation is performed according to the dispatching rules to obtain multiple scheduling indicators of the candidate operations. Scheduling is performed according to the scheduling indicators.

Claims

1. A tree search-based scheduling method, applicable to an electronic apparatus, the tree search-based scheduling method comprising:

receiving a plurality of order lists and initializing a schedule, wherein each of the order lists comprises a plurality of production operations;

selecting the production operation, which has not yet been joined into the schedule and is sorted foremost, in each of the order lists to acquire a plurality of prior operations of the order lists;

calculating an execution priority of the prior operations according to a plurality of dispatching rules, and selecting a plurality of candidate operations from the prior operations according to the execution priority;

listing the candidate operations as a next operation of the schedule respectively, and performing a scheduling simulation according to the dispatching rules to acquire a plurality of scheduling indicators of the candidate operations; and

performing the schedule according to the scheduling indicators.

2. The tree search-based scheduling method according to claim 1, further comprising:

creating a rule library, wherein the rule library records a plurality of available dispatching rules and a plurality of correlations between each of the available dispatching rules and a plurality of scheduling goals, wherein the scheduling indicators are associated with one of the scheduling goals.

3. The tree search-based scheduling method according to claim 2, further comprising:

selecting one of the scheduling goals; and

selecting the dispatching rules from the available dispatching rules according to the correlations between the available dispatching rules and the selected scheduling goal.

4. The tree search-based scheduling method according to claim 1, wherein calculating the execution priority of the prior operations according to the dispatching rules comprises:

sorting the prior operations respectively according to the dispatching rules; and

integrating a plurality of sorted results of the prior operations corresponding to the dispatching rules respectively to acquire the execution priority.

5. The tree search-based scheduling method according to claim 4, wherein integrating the sorted results of the prior operations corresponding to the dispatching rules respectively to acquire the execution priority comprises:

calculating a weighted average of the sorted results corresponding to the dispatching rules for each of the prior operations to calculate the execution priority.

6. The tree search-based scheduling method according to claim 1, wherein listing the candidate operations as the next operation of the schedule respectively, and performing the scheduling simulation according to the dispatching rules to acquire the scheduling indicators of the candidate operations comprises:

listing the candidate operations as the next operation of the schedule respectively to acquire a plurality of schedule pre-states corresponding to the candidate operations;

performing the scheduling simulation on the schedule pre-states respectively according to the dispatching rules to calculate a plurality of simulated scheduling results of the schedule pre-states corresponding to each of the dispatching rules; and

integrating the simulated scheduling results of the schedule pre-states corresponding to the dispatching rules respectively to acquire the scheduling indicators of the candidate operations.

7. The tree search-based scheduling method according to claim 6, wherein integrating the simulated scheduling results of the schedule pre-states corresponding to the dispatching rules respectively to acquire the scheduling indicators of the candidate operations comprises:

calculating a weighted average of the simulated scheduling results corresponding to the dispatching rules for each of the candidate operations to serve as the scheduling indicator of the candidate operation.

8. The tree search-based scheduling method according to claim 1, wherein the scheduling indicators comprise a best scheduling indicator and a second best scheduling indicator, wherein performing the schedule according to the scheduling indicators comprises:

selecting the candidate operation corresponding to the best scheduling indicator as an elected operation; and

joining the elected operation as the next operation of the schedule.

9. The tree search-based scheduling method according to claim 8, further comprising:

repeating the steps to continue to select the production operation, which has not yet been joined into the schedule and is sorted foremost, in each of the order lists to acquire a plurality of prior operations of the order lists, select a plurality of candidate operations from the prior operations, acquire a plurality of scheduling indicators of the candidate operations, and perform the schedule according to the scheduling indicators to select another elected operation from the production operations of the order lists;

joining the selected another elected operation as a next operation of the schedule when determining that the scheduling indicator of the selected another elected operation is superior to or equal to the second best scheduling indicator; and

replacing a last operation of the schedule with the candidate operation corresponding to the second best scheduling indicator when determining that the scheduling indicator of the selected another elected operation that is selected is inferior to the second best scheduling indicator.

10. The tree search-based scheduling method according to claim 9, wherein when determining that the scheduling indicator of the selected another elected operation is inferior to the second best scheduling indicator, the tree search-based scheduling method further comprises:

updating the scheduling indicator of the candidate operation corresponding to the best scheduling indicator.

11. An electronic apparatus, comprising:

a receiving device configured to receive data;

a storage device configured to store a plurality of modules; and

a processor coupled to the receiving device and the storage device and configured to load and execute the modules, wherein the modules comprise;

a data acquisition module configured to receive a plurality of order lists via the receiving device, wherein each of the order lists comprises a plurality of production operations;

a tree scheduling module configured to initialize a schedule;

a node filtering module configured to;

select the production operation, which has not yet been joined into the schedule and is sorted foremost, in each of the order lists to acquire a plurality of prior operations of the order lists; and

calculate an execution priority of the prior operations according to a plurality of dispatching rules, and select a plurality of candidate operations from the prior operations according to the execution priority; and

a node selection module configured to list the candidate operations as a next operation of the schedule respectively and perform a scheduling simulation according to the dispatching rules to acquire a plurality of scheduling indicators of the candidate operations,

wherein the tree scheduling module is further configured to perform the schedule according to the scheduling indicators.

12. The electronic apparatus according to claim 11, wherein the storage device is further configured to record a rule library, wherein the rule library records a plurality of available dispatching rules and a plurality of correlations between each of the available dispatching rules and a plurality of scheduling goals.

13. The electronic apparatus according to claim 12, wherein the processor selects one of the scheduling goals, and selects the dispatching rules from the available dispatching rules according to the correlations between the available dispatching rules and the selected scheduling goal.

14. The electronic apparatus according to claim 11, wherein the node filtering module is configured to:

sort the prior operations respectively according to the dispatching rules; and

integrate a plurality of sorted results of the prior operations corresponding to the dispatching rules respectively to acquire the execution priority.

15. The electronic apparatus according to claim 14, wherein the node filtering module is configured to:

calculate a weighted average of the sorted results corresponding to the dispatching rules for each of the prior operations to calculate the execution priority.

16. The electronic apparatus according to claim 11, wherein the node selection module is configured to:

list the candidate operations as the next operation of the schedule respectively to acquire a plurality of schedule pre-states corresponding to the candidate operations;

perform the scheduling simulation on the schedule pre-states respectively according to the dispatching rules to calculate a plurality of simulated scheduling results of the schedule pre-states corresponding to each of the dispatching rules; and

integrate the simulated scheduling results of the schedule pre-states corresponding to the dispatching rules respectively to acquire the scheduling indicators of the candidate operations.

17. The electronic apparatus according to claim 16, wherein the node selection module is configured to:

calculate a weighted average of the simulated scheduling results corresponding to the dispatching rules for each of the candidate operations to serve as the scheduling indicator of the candidate operation.

18. The electronic apparatus according to claim 11, wherein the scheduling indicators comprise a best scheduling indicator and a second best scheduling indicator, wherein the tree scheduling module is further configured to:

select the candidate operation corresponding to the best scheduling indicator as an elected operation; and

join the elected operation as the next operation of the schedule.

19. The electronic apparatus according to claim 18, wherein the processor is further configured to:

repeatedly execute the node filtering module and the node selection module to select another elected operation;

join the selected another elected operation as a next operation of the schedule when determining that the scheduling indicator of the selected another elected operation is superior to or equal to the second best scheduling indicator; and

replace a last operation of the schedule with the candidate operation corresponding to the second best scheduling indicator when determining that the scheduling indicator of the selected another elected operation is inferior to the second best scheduling indicator.

20. The electronic apparatus according to claim 19, wherein when determining that the scheduling indicator of the selected another elected operation is inferior to the second best scheduling indicator, the processor is further configured to:

update the scheduling indicator of the candidate operation corresponding to the best scheduling indicator.