In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No ma...In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. By normalizing all job sizes and machine cost, we assume that the cost of purchasing one machine is 1. We further know the total size of all jobs in advance. The objective is to minimize the sum of the makespan and the number of machines to be purchased. Both non-preemptive and preemptive versions are considered. For the non-preemptive version, we present a new lower bound 6/5 which improves the known lower bound 1.161. For the preemptive version, we present an optimal semi-online algorithm with a competitive ratio of 1 in the case that the total size is not greater than 4, and an algorithm with a competitive ratio of 5/4 otherwise, while a lower bound 1.0957 is also presented for general case.展开更多
This paper investigates a preemptive semi-online scheduling problem onm identical parallel machines wherem=2,3. It is assumed that all jobs have their processing times in betweenp andrp (p > 0,r ≥1). The goal is t...This paper investigates a preemptive semi-online scheduling problem onm identical parallel machines wherem=2,3. It is assumed that all jobs have their processing times in betweenp andrp (p > 0,r ≥1). The goal is to minimize the makespan. Best possible algorithms are designed for anyr≥1 whenm=2,3. Keywords semi-online - scheduling - preemption - competitive ratio Regular PaperThis research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE. China, and the National Natural Science Foundation of China (Grant Nos. 10271110 and 60021201).Yong He received his B.S., M.S., and Ph.D. degrees all from Zhejiang University in 1989, 1992, 1996, respectively. He is currently a professor and Ph.D. supervisor at Department of Mathematics, Zhejiang University. His current research interests include combinatorial and network optimization, scheduling theory, computational biology, mathematical modeling, etc.Yi-Wei Jiang received his B.S. degree from Zhejiang University in 2002. He is currently a Ph.D. candidate of Zhejiang University. His current interests include scheduling theory and online algorithms.展开更多
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in...Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.展开更多
A micro-flow injection sorbent extraction preconcentration system was combined with a graphite furnace atomic absorption spectrometry that formed an integrated system for the determination of trace amounts of elements...A micro-flow injection sorbent extraction preconcentration system was combined with a graphite furnace atomic absorption spectrometry that formed an integrated system for the determination of trace amounts of elements. The analytical performances of the prospsed method for determining Cd, Cu and Mn were studied. The analytes were preconcentrated with a thiol resin(Type 190, produced by Nankai University, China) whose active group is -SH. The elements to be determined were preconcentrated onto the column for 60 s and then rinsed with deionized water and eluted with 30 μL of 1 mol/L HCl. The graphite furnace atomic absorption spectrometry(GFAAS) determination of the concentrated analyte was carried out in parallel with the next preconcentration cycle. Enrichment factors 41, 22 and 20 and detection limits(3 σ , n =10) 0.36, 3.8 and 7.0 ng/L for Cd, Cu and Mn, respectively, along with a sampling frequency of 20 h -1 , were obtained with a 60 s loading time at a sample flow rate of 3.5 mL/min. The analytical results for a number of water samples show that the flow-injection semi-online column preconcentration can not only eliminate the effect of some concomitant elements, such as Li, Na, K, Ca and Mg, on the determination of the analyte, but also enhance the sensitivity.展开更多
This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or...This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least （2m-3）/（m-1） for any m〉2 and present optimal semi-online algorithms for m = 2, 3.展开更多
This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 〈 s1 = s2 = r 〈 t = s3, a...This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 〈 s1 = s2 = r 〈 t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max（2, 3s＋6/s＋6 is presented. We also show the lower bound is at least max（2, 38 3s/s＋6）. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.展开更多
In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when bot...In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞）, and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s 〉 （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）. The competitive ratio of the algorithms is （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）, which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem.展开更多
Ordinal online schedule for jobs with similar sizes in on two parallel machines system is considered. Firstly it is proved that the worst case performance ratio of the existing algorithm P2 cannot be improved even if ...Ordinal online schedule for jobs with similar sizes in on two parallel machines system is considered. Firstly it is proved that the worst case performance ratio of the existing algorithm P2 cannot be improved even if the job processing times are known in for any . Then a better algorithm named S is developed and its worst case performance ratio is given for? .展开更多
The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems. In this paper, two semi-online parallel machine scheduling problems with linear deterioration processi...The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems. In this paper, two semi-online parallel machine scheduling problems with linear deterioration processing time are considered. In the first problem, it is assumed that the deterioration rates of jobs are known in an interval, that is, bj ∈[0, α], where 0 〈α≤ 1 and bj denotes the linear deterioration rate. In the second problem, it is assumed that the largest deterioration rate of jobs is known in advance, that is, b = max1≤j≤n {bj }. For each of the two problems, a heuristic MBLS algorithm is worked out and its worst-case ratio is analyzed. At the same time, the worst-case ratio of the list （LS） algorithm is investigated and it is proved that all the ratios are tight.展开更多
研究半在线模型的松弛,讨论以下半在线松弛模型:已知工件最大加工时间在某一区域内(known largest jobinterval),分别讨论了该模型下2台同型机的极小化Cmax问题和极大化Cmin问题.对这两个问题构造pInterval算法,给出其竞争比并证明它是...研究半在线模型的松弛,讨论以下半在线松弛模型:已知工件最大加工时间在某一区域内(known largest jobinterval),分别讨论了该模型下2台同型机的极小化Cmax问题和极大化Cmin问题.对这两个问题构造pInterval算法,给出其竞争比并证明它是紧的,还分析了上述两个问题的特征和LS算法的竞争比.展开更多
基金Research supported by the Natural Science Foundation of Zhejiang Province （Grant No. Y605316）, and Natural Science Foundation of Education Department of Zhejiang Province （Grant No. 20060578）.
文摘In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. By normalizing all job sizes and machine cost, we assume that the cost of purchasing one machine is 1. We further know the total size of all jobs in advance. The objective is to minimize the sum of the makespan and the number of machines to be purchased. Both non-preemptive and preemptive versions are considered. For the non-preemptive version, we present a new lower bound 6/5 which improves the known lower bound 1.161. For the preemptive version, we present an optimal semi-online algorithm with a competitive ratio of 1 in the case that the total size is not greater than 4, and an algorithm with a competitive ratio of 5/4 otherwise, while a lower bound 1.0957 is also presented for general case.
文摘This paper investigates a preemptive semi-online scheduling problem onm identical parallel machines wherem=2,3. It is assumed that all jobs have their processing times in betweenp andrp (p > 0,r ≥1). The goal is to minimize the makespan. Best possible algorithms are designed for anyr≥1 whenm=2,3. Keywords semi-online - scheduling - preemption - competitive ratio Regular PaperThis research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE. China, and the National Natural Science Foundation of China (Grant Nos. 10271110 and 60021201).Yong He received his B.S., M.S., and Ph.D. degrees all from Zhejiang University in 1989, 1992, 1996, respectively. He is currently a professor and Ph.D. supervisor at Department of Mathematics, Zhejiang University. His current research interests include combinatorial and network optimization, scheduling theory, computational biology, mathematical modeling, etc.Yi-Wei Jiang received his B.S. degree from Zhejiang University in 2002. He is currently a Ph.D. candidate of Zhejiang University. His current interests include scheduling theory and online algorithms.
基金Project supported by the National Natural Science Foundation of China (Nos. 10271110 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE+2 种基金 China Project supported by the National Natural Science Foundation of China (Nos. 10271110 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE China
文摘Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.
文摘A micro-flow injection sorbent extraction preconcentration system was combined with a graphite furnace atomic absorption spectrometry that formed an integrated system for the determination of trace amounts of elements. The analytical performances of the prospsed method for determining Cd, Cu and Mn were studied. The analytes were preconcentrated with a thiol resin(Type 190, produced by Nankai University, China) whose active group is -SH. The elements to be determined were preconcentrated onto the column for 60 s and then rinsed with deionized water and eluted with 30 μL of 1 mol/L HCl. The graphite furnace atomic absorption spectrometry(GFAAS) determination of the concentrated analyte was carried out in parallel with the next preconcentration cycle. Enrichment factors 41, 22 and 20 and detection limits(3 σ , n =10) 0.36, 3.8 and 7.0 ng/L for Cd, Cu and Mn, respectively, along with a sampling frequency of 20 h -1 , were obtained with a 60 s loading time at a sample flow rate of 3.5 mL/min. The analytical results for a number of water samples show that the flow-injection semi-online column preconcentration can not only eliminate the effect of some concomitant elements, such as Li, Na, K, Ca and Mg, on the determination of the analyte, but also enhance the sensitivity.
基金support by the Teaching and Research Award Program for Outstanding Young Teachers in Higer Education Institutions of MOE,Chinaby National Natural Science Foundation of China (10271110, 60021201)
文摘This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least （2m-3）/（m-1） for any m〉2 and present optimal semi-online algorithms for m = 2, 3.
基金Supported by the National Natural Science Foundation of China (No. 60674071)
文摘This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 〈 s1 = s2 = r 〈 t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max（2, 3s＋6/s＋6 is presented. We also show the lower bound is at least max（2, 38 3s/s＋6）. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.
基金National Natural Science Foundation of"China(10271110,60021201)the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE,China
文摘In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞）, and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s 〉 （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）. The competitive ratio of the algorithms is （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）, which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem.
文摘Ordinal online schedule for jobs with similar sizes in on two parallel machines system is considered. Firstly it is proved that the worst case performance ratio of the existing algorithm P2 cannot be improved even if the job processing times are known in for any . Then a better algorithm named S is developed and its worst case performance ratio is given for? .
文摘The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems. In this paper, two semi-online parallel machine scheduling problems with linear deterioration processing time are considered. In the first problem, it is assumed that the deterioration rates of jobs are known in an interval, that is, bj ∈[0, α], where 0 〈α≤ 1 and bj denotes the linear deterioration rate. In the second problem, it is assumed that the largest deterioration rate of jobs is known in advance, that is, b = max1≤j≤n {bj }. For each of the two problems, a heuristic MBLS algorithm is worked out and its worst-case ratio is analyzed. At the same time, the worst-case ratio of the list （LS） algorithm is investigated and it is proved that all the ratios are tight.
文摘研究半在线模型的松弛,讨论以下半在线松弛模型:已知工件最大加工时间在某一区域内(known largest jobinterval),分别讨论了该模型下2台同型机的极小化Cmax问题和极大化Cmin问题.对这两个问题构造pInterval算法,给出其竞争比并证明它是紧的,还分析了上述两个问题的特征和LS算法的竞争比.
