Minimizing makespan on a single machine subject to random breakdowns

We investigate optimal sequencing policies for the expected makespan problem with an unreliable machine, where jobs have to be reprocessed in their entirety if preemptions occur because of breakdowns. We identify a class of uptime distributions under which LPT minimizes expected makespan.     

On weighting two criteria with a parameter in combinatorial optimization problems

Two criteria in a combinatorial problem are often combined in a weighted sum objective using a weighting parameter between 0 and 1. For special problem types, e.g., when one of the criteria is a bottleneck value, efficient algorithms are known that solve for a given value of the weighting parameter.     

Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date

We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.     

Counting and enumeration complexity with application to multicriteria scheduling

In this paper we tackle an important point of combinatorial optimisation: that of complexity theory when dealing with the counting or enumeration of optimal solutions. Complexity theory has been initially designed for decision problems and evolved over the years, for instance, to tackle particular features in optimisation problems. It has also evolved, more or less recently, towards the complexity of counting and enumeration problems and several complexity classes, which we review in this paper, have emerged in the literature. This kind of problems makes sense, notably, in the case of multicriteria optimisation where the aim is often to enumerate the set of the so-called Pareto optima. In the second part of this paper we review the complexity of multicriteria scheduling problems in the light of the previous complexity results.Received: November 2004 / Received version: March 2005MSC classification: 90B40, 90C29, 68Q15     

A Flexible On-line Scheduling Algorithm for Batch Machine with Infinite Capacity

We study on-line scheduling on a batch machine with infinite capacity. We present a flexible on-line scheduling algorithm that aims at minimizing the makespan and achieves the optimal competitive ratio of . This research is substantially supported by a grant from City University of Hong Kong (Grant No. 7001119). The second author is supported by this grant and by the Natural Science Foundation of China.     

江苏省区域经济发展水平实证分析--时序多指标综合评价方法及应用

区域经济发展水平是政策制定和管理决策的基础。不同于通常的静态评价方法,本文采用了一种时序多指标的系统工程评价方法,首先对时序多指标数据进行标准化处理,接着求出评价指标和评价年份各自的加权系数,然后确定出各年度的和综合的经济效益评价值,据此进行了聚类分析,将江苏省13个地区分成五类,最后根据评价结果提出一些政策建议。     

多车场有时间窗的多车型车辆调度及其禁忌算法研究

本文针对物流配送中的多车场车辆调度问题提出了两种多车场的处理方法，介绍了多车场车辆调度问题中容量、时间窗、多车型等多种约束的处理方法，并且根据具体约束情况设计了禁忌算法，对多车场有时间窗的多车型车辆调度问题加以实现，给出了一个具有代表性的算例试验结果和结果分析，通过试验表明了此方法对优化有时间窗的多车型车辆调度问题的有效性．     

MDD函数在单机总误工排序问题中的作用

本文把工件的修正工期（MDD：Modified Due Date）看成工件关于时间的函数，通过研究该函数在一定区间的性质建立了一个具有全局意义的定理，利用这个定理可以方便地导出有关单机总误工排序问题的一些重要结论．这些工作既能够很好地解释常用的MI）D规则的有效性，同时也说明MDD函数可以成为解决单机总误工排序问题的基本工具．     

带到达时间的单机排序中的资源分配问题

讨论两个单机排序的资源分配问题1｜rj,pj=bj-ajuj,Cmax≤｜∑uj和1｜rj,prec,pj=bj-ajuj C max≤｜∑uj并给出求其最优资源分配的多项式算法.