In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where V is a set of nodes, E is a set of edges with a non-negative transit-time function...In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where V is a set of nodes, E is a set of edges with a non-negative transit-time function . For each node , a time window ?within which the node may be visited and ?, is non-negative of the service and leaving time of the node. A source node s, a destination node d and a departure time?t0, the time-dependent shortest path problem with time windows asks to find an s, d-path that leaves a source node s at a departure time t0;and minimizes the total arrival time at a destination node d. This formulation generalizes the classical shortest path problem in which ce are constants. Our algorithm of the time windows gave the generalization of the ALT algorithm and A* algorithm for the classical problem according to Goldberg and Harrelson [1], Dreyfus [2] and Hart et al. [3].展开更多
Theoretical research often assumes all users arc homogeneous in their route choice decision and will always pick the route with the shortest travel cost,which is not necessarily the case in reality.This paper document...Theoretical research often assumes all users arc homogeneous in their route choice decision and will always pick the route with the shortest travel cost,which is not necessarily the case in reality.This paper documents the research effort in developing a Constrained Time-Dependent K Shortest Paths Algorithm inorder to find K Shortest Paths between two given locations.The goal of this research is to provide sound route options to travelers in order to assist their route choice decision process,during which the overlap and travel time deviation issues between the K paths will be considered.The proposed algorithm balancing overlap and travel time deviation is developed in this research.A numerical analysis is conducted on the Tucson 1-10 network,the outcome of the case study shows that our proposed algorithm is able to find different shortest paths with a reasonable degree of similarity and close travel time,which indicates that the result of the proposed algorithm is satisfactory.展开更多
In network with a shared channel in TDMA mechanism, it is a core issue to effectively allocate channel time to provide service guarantees for flows with QoS requirements. This paper proposes a simple and efficient tim...In network with a shared channel in TDMA mechanism, it is a core issue to effectively allocate channel time to provide service guarantees for flows with QoS requirements. This paper proposes a simple and efficient time allocation scheme called MES-ESRPT (MCTA at the End of Superframe-Enhanced Shortest Remaining Processing Time) for delay-sensitive VBR traffic in accordance with IEEE 802.15.3 standard. In this algorithm, PNC (piconet coordinator) allocates one MCTA (Management Channel Time Allocation) for each stream which is the process of communication at the end of superframe. During the MCTA period, each transmitter should report current fragments number of the first MSDU (MAC Service Data Unit) and the fragments number of the remainder MSDUs to PNC. In the next superframe, PNC firstly allocates part CTAs (Channel Time Allocation) for each stream based on the remainder fragments number of the first MSDU by SRPT rule, then allocates remainder CTAs for each stream based on all fragments number of remainder MSDUs by the same SRPT rule. Simulation results showed that our proposed MES-ESRPT method achieves significantly better performance in QoS for multimedia streams compared to the existing schemes.展开更多
In this paper, a fabrication scheduling problem concerning the production of components at a single manufacturing facility was studied, in which the manufactured components are subsequently assembled into a finite num...In this paper, a fabrication scheduling problem concerning the production of components at a single manufacturing facility was studied, in which the manufactured components are subsequently assembled into a finite number of end products. Each product was assumed to comprise a common component to all jobs and a unique component to itself. Common operations were processed in batches and each batch required a setup time. A product is completed when both its two operations have been processed and are available. The optimality criterion considered was the minimization of weighted flow time. For this scheduling problem, the optimal schedules were described in a weignted shortest processing time first （WSPT） order and two algorithms were constructed corresponding to the batch availability and item availability, respectively.展开更多
文摘In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where V is a set of nodes, E is a set of edges with a non-negative transit-time function . For each node , a time window ?within which the node may be visited and ?, is non-negative of the service and leaving time of the node. A source node s, a destination node d and a departure time?t0, the time-dependent shortest path problem with time windows asks to find an s, d-path that leaves a source node s at a departure time t0;and minimizes the total arrival time at a destination node d. This formulation generalizes the classical shortest path problem in which ce are constants. Our algorithm of the time windows gave the generalization of the ALT algorithm and A* algorithm for the classical problem according to Goldberg and Harrelson [1], Dreyfus [2] and Hart et al. [3].
文摘Theoretical research often assumes all users arc homogeneous in their route choice decision and will always pick the route with the shortest travel cost,which is not necessarily the case in reality.This paper documents the research effort in developing a Constrained Time-Dependent K Shortest Paths Algorithm inorder to find K Shortest Paths between two given locations.The goal of this research is to provide sound route options to travelers in order to assist their route choice decision process,during which the overlap and travel time deviation issues between the K paths will be considered.The proposed algorithm balancing overlap and travel time deviation is developed in this research.A numerical analysis is conducted on the Tucson 1-10 network,the outcome of the case study shows that our proposed algorithm is able to find different shortest paths with a reasonable degree of similarity and close travel time,which indicates that the result of the proposed algorithm is satisfactory.
基金Project supported by the National Natural Science Foundation of China (No. 60432030) and Distinguished Young Scholars of the Natural Science Foundation of China (No. 60525111)
文摘In network with a shared channel in TDMA mechanism, it is a core issue to effectively allocate channel time to provide service guarantees for flows with QoS requirements. This paper proposes a simple and efficient time allocation scheme called MES-ESRPT (MCTA at the End of Superframe-Enhanced Shortest Remaining Processing Time) for delay-sensitive VBR traffic in accordance with IEEE 802.15.3 standard. In this algorithm, PNC (piconet coordinator) allocates one MCTA (Management Channel Time Allocation) for each stream which is the process of communication at the end of superframe. During the MCTA period, each transmitter should report current fragments number of the first MSDU (MAC Service Data Unit) and the fragments number of the remainder MSDUs to PNC. In the next superframe, PNC firstly allocates part CTAs (Channel Time Allocation) for each stream based on the remainder fragments number of the first MSDU by SRPT rule, then allocates remainder CTAs for each stream based on all fragments number of remainder MSDUs by the same SRPT rule. Simulation results showed that our proposed MES-ESRPT method achieves significantly better performance in QoS for multimedia streams compared to the existing schemes.
文摘In this paper, a fabrication scheduling problem concerning the production of components at a single manufacturing facility was studied, in which the manufactured components are subsequently assembled into a finite number of end products. Each product was assumed to comprise a common component to all jobs and a unique component to itself. Common operations were processed in batches and each batch required a setup time. A product is completed when both its two operations have been processed and are available. The optimality criterion considered was the minimization of weighted flow time. For this scheduling problem, the optimal schedules were described in a weignted shortest processing time first （WSPT） order and two algorithms were constructed corresponding to the batch availability and item availability, respectively.
