A Characterization of PM-compact Hamiltonian Bipartite Graphs

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. A graph is called perfect matching compact（shortly, PM-compact）, if its perfect matching polytope has diameter one. This paper gives a complete characterization of simple PM-compact Hamiltonian bipartite graphs. We first define two families of graphs, called the H2C-bipartite graphs and the H23-bipartite graphs, respectively. Then we show that, for a simple Hamiltonian bipartite graph G with ｜V（G）｜ ≥ 6, G is PM-compact if and only if G is K3,3, or G is a spanning Hamiltonian subgraph of either an H2C-bipartite graph or an H23-bipartite graph.

Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery

This paper considers the integrated production and delivery scheduling on a serial batch machine,in which split is allowed in the delivery of the jobs.The objective is to minimize the makespan,i.e.,the maximum delivery completion time of the jobs.Lu et al.(Theor Comput Sci 572:50–57,2015)showed that this problem is strongly NP-hard,and presented a 32-approximation algorithm.In this paper,we present an improved 43-approximation algorithm for this problem.We also present a polynomial-time algorithm for the special case when all jobs have the identical weight.

Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan

We study an online(over time)scheduling problem on two uniform unbounded parallel-batch machines with processing speed 1 and v(0<≤1),respectively,to minimize the makespan.We first show that no online algorithm can have a competitive ratio less than 1+αL,whereαL=(√5−1)/2≈0.618 if 0≤1/2,andαL=α2(v)is the positive root ofα^(3)+3α^(2)+(3−1/v)α−1/v=0 if1/2≤1.This lower bound is still valid when all jobs have the same processing times.Then,we provide an online algorithm with a competitive ratio at most min{(√5+1)/2,√2/v}.When the jobs have the same processing times,we present the best possible online algorithm with a competitive ratio 1+αL.

PM-compact Graphs and Vertex-deleted Subgraphs

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings of G.A graph G is PM-compact if the 1-skeleton graph of the prefect matching polytope of G is complete.Equivalently,a matchable graph G is PM-compact if and only if for each even cycle C of G,G-V(C)has at most one perfect matching.This paper considers the class of graphs from which deleting any two adjacent vertices or nonadjacent vertices,respectively,the resulting graph has a unique perfect matching.The PM-compact graphs in this class of graphs are presented.

Task-assignment problem;Ternary variables;Binary variables;Mixed integer programming problem

We consider the online scheduling with job rejection to minimize the total weighted completion time of the scheduled jobs plus the total rejection penalty of the rejected jobs.In the problem,a set of independent jobs arriving online over time has to be scheduled with the flexibility of rejecting some of the jobs,where preemption is not allowed and the information of each job,including its processing time,release date,weight,and rejection penalty,is not known in advance.For this problem,using a technique named Greedy-Interval-Rejection,we provide an online algorithm with a competitive ratio of at most 4+εon identical machines and an online algorithm with a competitive ratio of at most 8 on unrelated machines,respectively。

Complexities of Some Problems on Multi-agent Scheduling on a Single Machine

We study the computational complexities of three problems on multi-agent scheduling on a single machine.Among the three problems,the computational complexities of the first two problems were still open and the last problem was shown to be unary NP-hard in the literature.We show in this paper that the first two problems are unary NP-hard.We also show that the unary NP-hardness proof for the last problem in the literature is invalid,and so,the exact complexity of the problem is still open.

Pareto Minimizing Total Completion Time and Maximum Cost with Positional Due Indices

In this paper,we study the Pareto optimization scheduling problem on a single machine with positional due indices of jobs to minimize the total completion time and a maximum cost.For this problem,we give two O(n^(4))-time algorithms.

Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems

Motivated by the problem to approximate all feasible schedules by one schedule in a given scheduling environment,we introduce in this paper the concepts of strong simultaneous approximation ratio and weak simultaneous approximation ratio.Then we study the two variants under various scheduling environments,such as non-preemptive,preemptive or fractional scheduling on identical,related or unrelated machines.

Equivalence of Some Different Maintenance Activities in Single-Machine Scheduling

We study single-machine scheduling problems with a single maintenance activity(MA)of length p0 under three types of assumptions:(A)the MA is required in a fixed time interval[T−p0,T]with T≥p0 and the job processing is of preemptive and resumable;(B)the MA is required in a relaxed time interval[0,T]with T≥p0 and the job processing is of nonpreemptive;(C)the MA is required in a relaxed time interval[T0,T]with 0≤T0≤T−p0 and the job processing is of nonpreemptive.We show in this paper that,up to the time complexity for solving scheduling problems,assumptions(A)and(B)are equivalent,and moreover,if T−(T0+p0)is greater than or equal to the maximum processing time of all jobs,the assumption(C)is also equivalent to(A)and(B).As an application,we study the scheduling for minimizing the weighted number of tardy jobs under the above three assumptions,respectively,and present corresponding time-complexity results.