This paper studies online scheduling of jobs with kind release times on a single machine. Here "kind release time" means that in online setting, no jobs can be released when the machine is busy. Each job J h...This paper studies online scheduling of jobs with kind release times on a single machine. Here "kind release time" means that in online setting, no jobs can be released when the machine is busy. Each job J has a kind release time r(J) ≥ 0, a processing time p(J) > 0 and a deadline d(J) > 0. The goal is to determine a schedule which maximizes total processing time( p(J)E(J)) or total number( E(J)) of the accepted jobs. For the first objective function p(J)E(J), we first present a lower bound 2(1/2), and then provide an online algorithm LEJ with a competitive ratio of 3. This is the first deterministic algorithm for the problem with a constant competitive ratio. When p(J) ∈ {1, k}, k > 1 is a real number, we first present a lower bound min{(1 + k)/k, 2 k/(1 + k)}, and then we show that LEJ has a competitive ratio of1 + k/k. In particular, when all the k length jobs have tight deadlines, we first present a lower bound max{4/(2 + k), 1}(for p(J)E(J)) and 4/3(for E(J)). Then we prove that LEJ is k/k-competitive for p(J)E(J) and we provide an online algorithm H with a competitive ratio of 2 k/( k + 1) for the second objective function E(J).展开更多
Hybrid rice significantly contributes to the food supply worldwide. Backbone parents play important roles in elite hybrid rice breeding systems. In this study, we performed pedigree-based analysis of the elite backbon...Hybrid rice significantly contributes to the food supply worldwide. Backbone parents play important roles in elite hybrid rice breeding systems. In this study, we performed pedigree-based analysis of the elite backbone parent rice variety, namely, Shuhui 527(SH527, Oryza sativa), to exploit key genome regions during breeding. Twenty-four cultivars(including SH527, its six progenitors and 17 derived cultivars) were collected and analyzed with high-density single nucleotide polymorphism(SNP) array. Scanning all these cultivars with genome-wide SNP data indicated the unique contributions of progenitors to the SH527 genome and identified the key genomic regions of SH527 conserved within all its derivatives. These findings were further supported by known rice yield-related genes or unknown QTLs identified by genome-wide association study. This study reveals several key regions for SH527 and provides insights into hybrid rice breeding.展开更多
基金Supported by the National Natural Science Foundation of China(11501279,11501171,11671188,and11401604)the Young Backbone Teachers of Luoyang Normal University(2018XJGGJS-10)Henan Colleges(2015GGJS-193)
文摘This paper studies online scheduling of jobs with kind release times on a single machine. Here "kind release time" means that in online setting, no jobs can be released when the machine is busy. Each job J has a kind release time r(J) ≥ 0, a processing time p(J) > 0 and a deadline d(J) > 0. The goal is to determine a schedule which maximizes total processing time( p(J)E(J)) or total number( E(J)) of the accepted jobs. For the first objective function p(J)E(J), we first present a lower bound 2(1/2), and then provide an online algorithm LEJ with a competitive ratio of 3. This is the first deterministic algorithm for the problem with a constant competitive ratio. When p(J) ∈ {1, k}, k > 1 is a real number, we first present a lower bound min{(1 + k)/k, 2 k/(1 + k)}, and then we show that LEJ has a competitive ratio of1 + k/k. In particular, when all the k length jobs have tight deadlines, we first present a lower bound max{4/(2 + k), 1}(for p(J)E(J)) and 4/3(for E(J)). Then we prove that LEJ is k/k-competitive for p(J)E(J) and we provide an online algorithm H with a competitive ratio of 2 k/( k + 1) for the second objective function E(J).
基金supported by the Sichuan Science and Technology Support Project, China (2016NZ0103)the National Natural Science Foundation of China (91435102 and 31570004)+1 种基金the Sichuan Provincial Founding for Distinguished Young Scholars, China (2015JQ0048)the Open Research Fund of State Key Laboratory of Hybrid Rice, Hunan Hybrid Rice Research Center, China (2016KF10)。
文摘Hybrid rice significantly contributes to the food supply worldwide. Backbone parents play important roles in elite hybrid rice breeding systems. In this study, we performed pedigree-based analysis of the elite backbone parent rice variety, namely, Shuhui 527(SH527, Oryza sativa), to exploit key genome regions during breeding. Twenty-four cultivars(including SH527, its six progenitors and 17 derived cultivars) were collected and analyzed with high-density single nucleotide polymorphism(SNP) array. Scanning all these cultivars with genome-wide SNP data indicated the unique contributions of progenitors to the SH527 genome and identified the key genomic regions of SH527 conserved within all its derivatives. These findings were further supported by known rice yield-related genes or unknown QTLs identified by genome-wide association study. This study reveals several key regions for SH527 and provides insights into hybrid rice breeding.
