We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into...We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint.Three problems are considered:(1)minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2)minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;(3)minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O(n2)time algorithm for the first problem.Moreover,for the other two problems,we first show that they are NP-hard,and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them,respectively.展开更多
In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is...In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is tight.展开更多
基金Supported by Key Research Projects of Henan Higher Education Institutions(20A110037)Young Backbone Teachers Training Program of Zhongyuan University of Technology(2018XQG15)+4 种基金Outstanding Youth Foundation of Science and Technology Innovation of Henan Province(184100510004)Natural Science Foundation of Henan Education Department(16A630061)Science and Technology Program of Henan Province(182102110129)Innovation Training Program for College Students of Henan Province(S201910485026)Basic Research Projects of Key Scientific Research Projects Plan in Henan Higher Education Institutions(20zx003)。
文摘We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint.Three problems are considered:(1)minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2)minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;(3)minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O(n2)time algorithm for the first problem.Moreover,for the other two problems,we first show that they are NP-hard,and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them,respectively.
基金Supported by the National Natural Sciences Youth Foundation(10901144)
文摘In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is tight.
