This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the n...This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the non-availability period will have to partially restartafter the machine has become available again. For the problem with objective of minimizingmakespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed.For the problem with objective of minimizing total weighted completion time, an approximationalgorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latterproblem are also considered, and improved algorithms are given.展开更多
This paper investigates several different semi-on-line two-machine scheduling problems for maximizing the minimum machine completion time. For each problem, we propose a best possible algorithm.
This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT a...This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.展开更多
Focusing on the ordinal scheduling problem on a parallel machine system, we discuss the background of ordinal scheduling and the motivation of ordinal algorithms. In addition, for the ordinal scheduling problem on ide...Focusing on the ordinal scheduling problem on a parallel machine system, we discuss the background of ordinal scheduling and the motivation of ordinal algorithms. In addition, for the ordinal scheduling problem on identical parallel machines with the objective to maximize the minimum machine load, we then give two asymptotically optimal algorithm classes which have worst-case ratios very close to the upper bound of the problem for any given m. These results greatly improve the results proposed by He Yong and Tan Zhiyi in 2002.展开更多
In real world situations, most scheduling problems occur neither as complete off-line nor as complete on-line models. Most likely, a problem arises as an on-line model with some partial information. In this article, w...In real world situations, most scheduling problems occur neither as complete off-line nor as complete on-line models. Most likely, a problem arises as an on-line model with some partial information. In this article, we consider such a model. We study the scheduling problem P(n1,n2), where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon as all jobs in the first group are assigned, the second job group appears. The objective is to minimize the longest job completion time (makespan). We show a lower bound of 3/2 even for very special cases. Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed for the general case. The main contribution of this paper is to discuss the impact of the quantity of available information in designing an on-line algorithm. It is interesting to note that the absence of even a little bit information may significantly affect the performance of an algorithm.展开更多
This paper considers parallel machine scheduling with special jobs. Normal jobs can be processed on any of the parallel machines, while the special jobs can only be processed on one machine. The problem is analyzed fo...This paper considers parallel machine scheduling with special jobs. Normal jobs can be processed on any of the parallel machines, while the special jobs can only be processed on one machine. The problem is analyzed for various manufacturing conditions and service requirements. The off-line scheduling problem is transformed into a classical parallel machine scheduling problem. The on-line scheduling uses the FCFS （first come, first served）, SWSC （special window for special customers）, and FFFS （first fit, first served） algorithms to satisfy the various requirements. Furthermore, this paper proves that FCFS has a competitive ratio of m, where m is the number of parallel machines, and this bound is asymptotically tight, SWSC has a competitive ratio of 2 and FFFS has a competitive ratio of 3- 2/m, and these bounds are tight.展开更多
A version of the k-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive a...A version of the k-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 for k≥3.展开更多
：We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information.
基金Supported by the National Natural Science Foundation of China(10971191, 60021201)Fundamental Research Funds for the Central Universities(2010QNA3040)the China Postdoctoral Science Foundation
文摘This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the non-availability period will have to partially restartafter the machine has become available again. For the problem with objective of minimizingmakespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed.For the problem with objective of minimizing total weighted completion time, an approximationalgorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latterproblem are also considered, and improved algorithms are given.
基金This research is supported by the National Natural Science Foundation of China (No,19701028).
文摘This paper investigates several different semi-on-line two-machine scheduling problems for maximizing the minimum machine completion time. For each problem, we propose a best possible algorithm.
基金the National Natural Science Foundation of China(10301028,60021201)A preliminary version of this paper appeared in the proceedings of the 1st International Conference on Algorithmic Applications in Management,Lecture Notes in Computer Science 3521
文摘This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.
文摘Focusing on the ordinal scheduling problem on a parallel machine system, we discuss the background of ordinal scheduling and the motivation of ordinal algorithms. In addition, for the ordinal scheduling problem on identical parallel machines with the objective to maximize the minimum machine load, we then give two asymptotically optimal algorithm classes which have worst-case ratios very close to the upper bound of the problem for any given m. These results greatly improve the results proposed by He Yong and Tan Zhiyi in 2002.
基金Research partially supported by a Hong Kong Government RGC Earmarked Grant.Ref.No.CUHK356/96E Research partially supported by National 973 Fundamental Research Project of china and National Natural Science Foundation of China (19801032)
文摘In real world situations, most scheduling problems occur neither as complete off-line nor as complete on-line models. Most likely, a problem arises as an on-line model with some partial information. In this article, we consider such a model. We study the scheduling problem P(n1,n2), where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon as all jobs in the first group are assigned, the second job group appears. The objective is to minimize the longest job completion time (makespan). We show a lower bound of 3/2 even for very special cases. Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed for the general case. The main contribution of this paper is to discuss the impact of the quantity of available information in designing an on-line algorithm. It is interesting to note that the absence of even a little bit information may significantly affect the performance of an algorithm.
基金Supported by the National Natural Science Foundation of China (No.70471008)
文摘This paper considers parallel machine scheduling with special jobs. Normal jobs can be processed on any of the parallel machines, while the special jobs can only be processed on one machine. The problem is analyzed for various manufacturing conditions and service requirements. The off-line scheduling problem is transformed into a classical parallel machine scheduling problem. The on-line scheduling uses the FCFS （first come, first served）, SWSC （special window for special customers）, and FFFS （first fit, first served） algorithms to satisfy the various requirements. Furthermore, this paper proves that FCFS has a competitive ratio of m, where m is the number of parallel machines, and this bound is asymptotically tight, SWSC has a competitive ratio of 2 and FFFS has a competitive ratio of 3- 2/m, and these bounds are tight.
文摘A version of the k-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 for k≥3.
基金This work is supported by NSF of China and Shandong Province and The Grant of Young and Middle-age Scientists in Shandong Provi
文摘：We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information.
