Flow Injection Semi-online Preconcentration Graphite Furnace Atomic Absorption Spectrometry for Determination of Cadmium,Copper and Manganese

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.

A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs

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.

Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times

In this paper,we consider the problem of semi-online machine covering on three machines with two hierarchies,whose objective is to maximize the minimum machine load.Since there is no online algorithm with bounded competitive ratio for the online machine covering problem,we consider the semi-online case where the processing times of all jobs lie in[1,α].When there are one machine of hierarchy 1 and two machines of hierarchy 2,we design an optimal online algorithm with a competitive ratio of 1+α.When there are two machines of hierarchy 1 and one machine of hierarchy 2,we give an optimal online algorithm with a competitive ratio of 1+2α.

Semi-Online Algorithms for Scheduling with Machine Cost

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.

Preemptive Semi-Online Scheduling with Tightly-Grouped Processing Times

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.

Preemptive Semi-online Algorithms for Parallel Machine Scheduling with Known Total Size

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.

A Better Semi-online Algorithm for Q3/s_1=s_2≤s_3/C_(min) with the Known Largest Size

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.

Deterministic and randomized scheduling problems under the lp norm on two identical machines

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.

Better Algorithm of Ordinal Online Schedule for Jobs with Similar Sizes on Two Machines

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? .

Optimal Preemptive Online Algorithms for Scheduling with Known Largest Size on Two Uniform Machines

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.