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.展开更多
A型装箱问题(ASBP)是BP(Back ing Prob lem)的一种变型问题,与经典的BP问题不同的是,在ASBP中物品有两个参数:高度和半径。在装箱过程中,除了要求箱子中所有物品的高度和不大于1之外,还要求后到达的物品放在先到达的物品之上且上层物品...A型装箱问题(ASBP)是BP(Back ing Prob lem)的一种变型问题,与经典的BP问题不同的是,在ASBP中物品有两个参数:高度和半径。在装箱过程中,除了要求箱子中所有物品的高度和不大于1之外,还要求后到达的物品放在先到达的物品之上且上层物品的半径不超过下层物品的半径。分析了无穷数目的不同半径和有限数目的不同半径两种情形。对于无穷数目的不同半径的情形,我们证明了NF(Next F it)、FF(F irst F it)、BF(Best F it)、RBF(Rad ius Best F it)和AF(Any F it)算法的渐近最坏比为无穷大;对于有限数目的不同半径的情形,我们得到了FF、RBF算法的精确渐近最坏界。展开更多
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.
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.展开更多
文摘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.
文摘A型装箱问题(ASBP)是BP(Back ing Prob lem)的一种变型问题,与经典的BP问题不同的是,在ASBP中物品有两个参数:高度和半径。在装箱过程中,除了要求箱子中所有物品的高度和不大于1之外,还要求后到达的物品放在先到达的物品之上且上层物品的半径不超过下层物品的半径。分析了无穷数目的不同半径和有限数目的不同半径两种情形。对于无穷数目的不同半径的情形,我们证明了NF(Next F it)、FF(F irst F it)、BF(Best F it)、RBF(Rad ius Best F it)和AF(Any F it)算法的渐近最坏比为无穷大;对于有限数目的不同半径的情形,我们得到了FF、RBF算法的精确渐近最坏界。
基金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.
基金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.
