Scheduling with families of jobs and delivery coordination under job availability

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 $O(nlogn)$-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 $O\left(f^2{n}^f\right)$-time dynamic programming algorithm, where $n$ is the number of jobs, and $f$ is the number of families; we also provide a heuristic algorithm with a performance ratio of 3/2.     

Efficient algorithms for the round-trip 1-center and 1-median problems

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 $A^i\subseteq A$ of depots that i can potentially select from and use. When $A^i=A$ for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an $O(mn\lg n)$-time algorithm. For the restricted 1-median problem, we give an $O(mn\lg (|A|/m)+n^2\lg n)$-time algorithm. For the unrestricted 1-median problem, we give an $O(mn+n^2\lg \lg n)$-time algorithm.     

Proximity and average eccentricity of a graph

Let $G=(V,E)$ be a connected graph on n vertices. The proximity $\pi (G)$ of G is the minimum average distance from a vertex of G to all others. The eccentricity $e(v)$ of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity $\mathit{ecc}(G)$ of the graph G is $\frac{1}{n}{\sum }_{v\in V(G)}e(v)$. Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on $n?3$ vertices, $\mathit{ecc}(G)?\pi (G)?\mathit{ecc}(P_n)?\pi (P_n)$, with equality if and only if $G?P_n$. In this paper, we show that this conjecture is true.     

Efficient dominating sets in circulant graphs with domination number prime

Cayley graphs of finite cyclic group ${\mathbb{Z}}_n$ are called circulant graphs and denoted by $\mathrm{Cay}({\mathbb{Z}}_n,S)$. For $\mathrm{Cay}({\mathbb{Z}}_n,S)$ with $\frac{n}{|S|+1}$ prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets.     

Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph $G=(V,E)$ with edge-weights $w:E\to {\mathbb{R}}_{\ge 0}$ and vertex-weights $\eta :V\to {\mathbb{R}}_{+}$ are given. The goal is to find a vertex set $S\subseteq V$ with $|S|\le t$ while minimizing $w(S,V\backslash S)/\eta (S)$, where $w(S,V\backslash S)$ is the total weight of the edges with exactly one endpoint in S and $\eta (S)={\sum }_{v\in S}\eta (v)$. For this problem, we present a $(O(\log t),1+ϵ)$ factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when $t=n^{o(1)}$. We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.     

Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication

In a distributed computing environment, the schedule by which tasks are assigned to processors is critical to minimizing the overall run-time of the application. However, the problem of discovering the schedule that gives the minimum finish time is NP-Complete. This paper addresses static scheduling of a directed a-cyclic task graph (DAG) on a heterogeneous, bounded set of distributed processors to minimize the makespan. By combining several innovative techniques, including insertion-based scheduling and multiple task duplication, we present a new heuristic, known as Heterogeneous N-predecessor Decisive Path (HNDP), for scheduling directed a-cyclic weighted task graphs (DAGs) on a set of heterogeneous processors. We compare the performance of HNDP, under a range of varying input conditions, with two of the best existing heterogeneous heuristics namely HEFT and STDS. The results presented in this paper show that HNDP outperforms the two heuristics in terms of finish time and the number of processors employed over a wide range of parameters. The complexity of HNPD is $O(v^{2.}p)$ vs. $O(v^{2.}p)$ of HEFT and $O(v^2)$ of STDS where $v$ is the number of nodes in the DAG.     

Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges

Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to $2\lfloor \frac{n(G)}{2}\rfloor$, where $n(G)$ is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to $n(G)$, where $r\ge 3$. 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 $n(G)$, $n(H)\ge$ 9, let $k_1$, $k_2\ge 5$ 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 $G\times H$ with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of ${\mathit{NQ}}_{m_r,\dots ,m_1}$ and ${\mathit{GQ}}_{m_r,\dots ,m_1}$.