Single-machine online scheduling of jobs with non-delayed processing constraint

Journal of Combinatorial Optimization - This paper introduces a new environment of online scheduling in which jobs are scheduled under the non-delayed processing (NDP) constraint, where NDP means...     

An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities

We consider the online (over time) scheduling on a single unbounded parallel-batch machine with job processing time compatibilities to minimize makespan. In the problem, a constant \(\alpha >0\) is given in advance. Each job \(J_{j}\) has a normal processing time \(p_j\). Two jobs \(J_i\) and \(J_j\) are compatible if \(\max \{p_i, p_j\} \le (1+\alpha )\cdot \min \{p_i, p_j\}\). In the problem, mutually compatible jobs can form a batch being processed on the machine. The processing time of a batch is equal to the maximum normal processing time of the jobs in this batch. For this problem, we provide an optimal online algorithm with a competitive ratio of \(1+\beta _\alpha \), where \(\beta _\alpha \) is the positive root of the equation \((1+\alpha )x^{2}+\alpha x=1+\alpha \).     

A note on special optimal batching structures to minimize total weighted completion time

A batch is a subset of jobs which must be processed jointly in either serial or parallel form. The algorithmic aspects of the batching scheduling problems have been extensively studied in the literature. This paper presents necessary and sufficient conditions of the existence of optimal batch sequences for the single machine, batching, total weighted completion time scheduling problems on two batching ways: (1) all jobs form one batch; (2) each batch contains a single job. This kind of conditions can help us to recognize some special optimal schedules quickly. Research supported by NSFC (10671183).     

Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart

We consider the online scheduling of equal length jobs on unbounded parallel batch processing machines to minimize makespan with limited restart. In the problem \(m\) identical unbounded parallel batch processing machines are available to process the equal length jobs arriving over time. The processing batches are allowed limited restart. Here, “restart” means that a running task may be interrupted, losing all the work done on it, and the jobs in the interrupted task are then released and become independently unscheduled jobs, called restarted jobs. “Limited restart” means that only a running batch that contains no restarted jobs can be restarted. For this problem, we present a best possible online algorithm.     

A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times

We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J _j , its processing time and delivery time are denoted by p _j and q _j , respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J _j , q _j ≤p _j ; (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J _i and J _j , p _i >p _j implies q _i ≥q _j . We provide an on-line algorithm with competitive ratio for both problems, and the results are the best possible. Project supported by NSFC (10671183).     

Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan

We consider the scheduling of n family jobs with release dates on m identical parallel batching machines. Each batching machine can process up to b jobs simultaneously as a batch. In the bounded model, b<n, and in the unbounded model, b=∞. Jobs from different families cannot be placed in the same batch. The objective is to minimize the maximum completion time (makespan). When the number of families is a constant, for both bounded model and unbounded model, we present polynomial-time approximation schemes (PTAS).     

Online scheduling to minimize the total weighted completion time plus the rejection cost

We consider the online scheduling on a single machine, in which jobs are released over time and each job can be either accepted and scheduled on the machine or rejected under a certain rejection cost. The goal is to minimize the total weighted completion time of the accepted jobs plus the total rejection cost of the rejected jobs. For this problem, we provide an online algorithm with a best possible competitive ratio of 2.     

Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

In this paper, we consider the following single machine online tradeoff scheduling problem. A set of n independent jobs arrive online over time. Each job \(J_{j}\) has a release date \(r_{j}\), a processing time \(p_{j}\) and a delivery time \(q_{j}\). The characteristics of a job are unknown until it arrives. The goal is to find a schedule that minimizes the makespan \(C_{\max } = \max _{1 \le j \le n} C_{j}\) and the maximum lateness \(L_{\max } = \max _{1 \le j \le n} L_{j}\), where \(L_{j} = C_{j} + q_{j}\). For the problem, we present a nondominated \(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)-competitive online algorithm for each \(\rho \) with \( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\).     

滇越铁路与云南近代进出口贸易

滇越铁路是指云南昆明到越南河内的一条窄轨铁路,是法国侵略云南的见证,它的修建对云南近代政治经济、文化产生了巨大作用.本文通过对滇越铁路通车前后云南近代进出口贸易情况的对比,论述了滇越铁路的通车对云南近代进出口贸易的影响.     

论地域特征、地方经验与文学书写中的地方感——以愚园路为样本

《长恨歌》《繁花》《封锁》等与愚园路相关的小说屡获茅盾文学奖和鲁迅文学奖,使这条马路成为一个独特的文学场域.愚园路具有"近乎郊野、越界筑路、沪西歹土、新里文化、街区商业"等丰富的地域特征,这些地域特征通过作家的地方经验,化为作品中的"地方感",由"感知"而"态度",最后变成"价值观"和"世界观".本文采样分析了林语堂、张爱玲、王安忆、金宇澄、小白等作家的相关文本,试图阐明文学作品具有内在的地理学属性,它们往往成为地域意识的表达.文学作品不只是简单地对客观地理进行深情描写,同时也展示了情绪景观、阅历景观和知识景观,提供了认识不同地域的方法.熟悉于此的地方依恋和沉浸于此的历史认同所培养的"地方感"对作家书写有着潜移默化的影响,地域特征也有赖文学书写的隐喻空间得以非遗性保存,并构成值得回味的互文关系.我们不仅可以就此感受到社会空间如何通过地方意识投射到作家文本中,而且可以发现这些历时性的文学书写又如何回过来形塑了丰富的地域特征.