共查询到20条相似文献,搜索用时 375 毫秒
1.
2.
We consider in this paper the scheduling of families of jobs in which both processing and delivery are coordinated together. Only one vehicle is available to deliver the jobs to specified customers. The jobs can be processed together to form processing batches on the machine and setups of batches are required when the machine is changing from one family to another. Jobs from different families cannot be transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We propose an -time optimal algorithm for the scheduling problem under the group technology assumption. For the scheduling problem without the group technology assumption, we show that the problem is NP-hard and give an -time dynamic programming algorithm, where is the number of jobs, and is the number of families; we also provide a heuristic algorithm with a performance ratio of 3/2. 相似文献
3.
《Journal of Computer and System Sciences》2016,82(5):782-792
This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset of depots that i can potentially select from and use. When for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an -time algorithm. For the restricted 1-median problem, we give an -time algorithm. For the unrestricted 1-median problem, we give an -time algorithm. 相似文献
4.
5.
6.
《Journal of Computer and System Sciences》2016,82(5):793-801
7.
8.
9.
10.
11.
12.
Let be a connected graph on n vertices. The proximity of G is the minimum average distance from a vertex of G to all others. The eccentricity of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity of the graph G is . Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on vertices, , with equality if and only if . In this paper, we show that this conjecture is true. 相似文献
13.
14.
《Information Processing Letters》2014,114(12):700-702
Cayley graphs of finite cyclic group are called circulant graphs and denoted by . For with prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets. 相似文献
15.
16.
17.
18.
《Journal of Computer and System Sciences》2016,82(5):767-781
Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to , where is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to , where . A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where , 9, let , be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of and . 相似文献
19.
20.
Michael Thomas 《Information Processing Letters》2012,112(10):386-391
For decision problems defined over Boolean circuits using gates from a restricted set B only, we have for all finite sets B and of gates such that all gates from B can be computed by circuits over gates from . In this note, we show that a weaker version of this statement holds for decision problems defined over Boolean formulae, namely that and for all finite sets B and of Boolean functions such that all can be defined in . 相似文献