We study robust single-machine batch scheduling problems under uncertain processing times to min-imize total flow time. Two types of batches are considered: serial batch (s-batch) and parallel batch (p-batch). These p...
详细信息
We study robust single-machine batch scheduling problems under uncertain processing times to min-imize total flow time. Two types of batches are considered: serial batch (s-batch) and parallel batch (p-batch). These problems can model many on-site production and logistics applications which involve uncertain factors such as defect rates. We first prove that a sequencing rule for the shortest nominal processing time is optimal for both s-batch and p-batch problems. We then propose polynomial-timealgorithms based on the observation that the robust batch scheduling problems are reducible or par-tially reducible to a constrained shortest path problem through worst-case scenario analysis. We further present more efficient algorithms for the special case of uniform maximum deviation times for all jobs. The algorithms are evaluated computationally, and the results show that their performance is satisfactory on the tested instances. (c) 2022 Elsevier B.V. All rights reserved.
This paper introduces an optimal method entitled Dhouib-Matrix-SPP (DM-SPP) in order to solve the Shortest Path Problem with a complexity time of 0 (n + m) where n and m are respectively the number of vertices and edg...
详细信息
This paper introduces an optimal method entitled Dhouib-Matrix-SPP (DM-SPP) in order to solve the Shortest Path Problem with a complexity time of 0 (n + m) where n and m are respectively the number of vertices and edges. DM-SPP is a rapid method, it can reduce reasonably the research time and consequently the running time as well as the energy consumption. It is composed of five simple steps repeated in (n-1) iterations and for more clarification a guided step-by-step application of the novel method DM-SPP is presented. Moreover, several examples are solved wherein a fully complete and random distribute graphs are analyzed with the variation of the number of vertices from 20 to 6000 and the number of edges from 49 to 17097565. DM-SPP is coded under Python programming language and all experimental results demonstrate that DM-SPP can rapidly generate the optimal short path. Furthermore, by comparing the complexity time required by DM-SPP to the time prerequisite by Dijkstra algorithm, it can be concluded that DM-SPP and Dijkstra are concurrent for small instances and for larger instances DM-SPP can easily outperform Dijkstra and especially for the case of incomplete undirected graphs which are more realistic in the real-world viewing that all graphs are really not complete. The performance of DM-SPP is statistically confirmed with the Mann-Whitney U nonparametric test Further research trends will focus on the test of DM-SPP for the uncertain Shortest Path problem and the resolution of the autonomous mobile robot path planning problem.
暂无评论