【摘 要】
：
In this paper, we consider the problem of scheduling jobs with release dates and rejection on a bounded single parallel batching machine.Our objective is to minimize the sum of total completion time o
【机 构】
：
School of Computer Science and Technology,Shandong University,Jinan 250101,China
【出 处】
：
2015全国理论计算机科学学术年会
论文部分内容阅读
In this paper, we consider the problem of scheduling jobs with release dates and rejection on a bounded single parallel batching machine.Our objective is to minimize the sum of total completion time of the accepted jobs and the total penalty of the rejected jobs.We need to determine how to choose jobs for processing, divide these jobs into batches, and sequence these batches so that the objective function is minimized.We give a simplified enumeration approximation scheme for this problem by applying combinatorial optimization techniques with delicate analysis.
其他文献
为建立鲜切蔬菜的货架期预测模型,在冰温储藏下,通过正交设计确定了菠菜鲜切处理的最佳方案为用75mg/LCLO2水溶液、0.5％NaCl溶液分别浸泡10min后,PVDC保鲜膜包装.通过对鲜切菠菜相关理化指标、菌落总数的测定及感官评价,跟踪样品品质随时间、温度的变化关系.结果表明,菠菜叶绿素含量随着贮藏时间的延长分别呈现出逐渐升高和降低的趋势.随着贮藏温度的升高,菠菜相关的各品质指标变化率也增大,且
为了探明猴头菇褐变机制并抑制褐变,研究了柠檬酸处理和贮藏温度对猴头菇褐变度、总酚含量、多酚氧化酶(PPO)活性、过氧化物酶(POD)活性的影响.结果表明,猴头菇在(15±0.5)℃条件下贮藏褐变严重,而(1±0.5)℃下贮藏能有效抑制其褐变,柠檬酸处理后在(15±0.5)℃条件下贮藏依然褐变严重.总酚含量和PPO活性、POD活性与猴头菇褐变相关,但不是褐变的诱发原因.
In this paper, we restudy busy beaver problem that is defined by Tibor Rado in 1962.Based on his work, we describe four decision problems-busy beaver problerr, max shifter problem, halting empty tape
In this paper, a novel approach for initializing clustering centers of K-Means algorithm is presented.This method is based on the variance of dimension, which is used as keyword to make a full permuta
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs.The core of these programs are algorithms to solve kidney exch
Till now, the types of attacks for cryptographic device are usually distinguished as leakage and tampering attacks respectively.The former, also known as side-channel attacks, is described that when r
We consider a regular random (k, s)-SAT problem.We show that for all k exceeding an absolute constant k0, with the clause density αureq > 2klog2-klog2/2 + εk, there is no satisfying assignments w.h.p.
Document databases are becoming popular, but how to present complex document query to obtain useful information from the document remains an important topic to study.In this paper, we describe the des
The individual household electricity consumption is major part of the city in the electricity market.The accurate prediction of household power load is very important for power sector to reasonable de
Herd behavior is a phenomenon that often appears in the stock market.It is caused by the irrational imitation of investors and is expressed as major investors make similar investing decisions in a sho