The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies ha...The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies have considered them simultaneously. This paper solves the integrated production and transportation scheduling problem(IPTSP) in hybrid flow shops, which is an extension of the hybrid flow shop scheduling problem(HFSP). In addition to the production scheduling on machines, the transportation scheduling process on automated guided vehicles(AGVs)is considered as another optimization process. In this problem, the transfer tasks of jobs are performed by a certain number of AGVs. To solve it, we make some preparation(including the establishment of task pool, the new solution representation and the new solution evaluation), which can ensure that satisfactory solutions can be found efficiently while appropriately reducing the scale of search space. Then, an effective genetic tabu search algorithm is used to minimize the makespan. Finally, two groups of instances are designed and three types of experiments are conducted to evaluate the performance of the proposed method. The results show that the proposed method is effective to solve the integrated production and transportation scheduling problem.展开更多
Fault tolerance has become an important issue in parallel computing. It is often addressed at system level, but application-level approaches receive increasing attention. We consider a parallel programming pattern, th...Fault tolerance has become an important issue in parallel computing. It is often addressed at system level, but application-level approaches receive increasing attention. We consider a parallel programming pattern, the task pool, and provide a fault-tolerant implementation in a library. Specifically, our work refers to lifeline-based global load balancing, which is an advanced task pool variant that is implemented in the GLB framework of the parallel programming language X10. The variant considers side effect-free tasks whose results are combined into a final result by reduction. Our algorithm is able to recover from multiple fail-stop failures. If recovery is not possible, it halts with an error message. In the algorithm, each worker regularly saves its local task pool contents in the main memory of a backup partner. Backups are updated for steals. After failures, the backup partner takes over saved copies and collects others. In case of multiple failures, invocations of the restore protocol are nested. We have implemented the algorithm by extending the source code of the GLB library. In performance measurements on up to 256 places, we observed an overhead between 0.5% and 30%. The particular value depends on the application’s steal rate and task pool size. Sources of performance overhead have been further analyzed with a logging component.展开更多
基金Supported by National Key R&D Program of China (Grant No. 2019YFB1704603)National Natural Science Foundation of China (Grant Nos. U21B2029 and 51825502)。
文摘The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies have considered them simultaneously. This paper solves the integrated production and transportation scheduling problem(IPTSP) in hybrid flow shops, which is an extension of the hybrid flow shop scheduling problem(HFSP). In addition to the production scheduling on machines, the transportation scheduling process on automated guided vehicles(AGVs)is considered as another optimization process. In this problem, the transfer tasks of jobs are performed by a certain number of AGVs. To solve it, we make some preparation(including the establishment of task pool, the new solution representation and the new solution evaluation), which can ensure that satisfactory solutions can be found efficiently while appropriately reducing the scale of search space. Then, an effective genetic tabu search algorithm is used to minimize the makespan. Finally, two groups of instances are designed and three types of experiments are conducted to evaluate the performance of the proposed method. The results show that the proposed method is effective to solve the integrated production and transportation scheduling problem.
文摘Fault tolerance has become an important issue in parallel computing. It is often addressed at system level, but application-level approaches receive increasing attention. We consider a parallel programming pattern, the task pool, and provide a fault-tolerant implementation in a library. Specifically, our work refers to lifeline-based global load balancing, which is an advanced task pool variant that is implemented in the GLB framework of the parallel programming language X10. The variant considers side effect-free tasks whose results are combined into a final result by reduction. Our algorithm is able to recover from multiple fail-stop failures. If recovery is not possible, it halts with an error message. In the algorithm, each worker regularly saves its local task pool contents in the main memory of a backup partner. Backups are updated for steals. After failures, the backup partner takes over saved copies and collects others. In case of multiple failures, invocations of the restore protocol are nested. We have implemented the algorithm by extending the source code of the GLB library. In performance measurements on up to 256 places, we observed an overhead between 0.5% and 30%. The particular value depends on the application’s steal rate and task pool size. Sources of performance overhead have been further analyzed with a logging component.
