堆取料机调度问题的一个近似算法

研究源自煤炭港口料场管理的堆取料机调度问题.该问题中,堆取料机从长为L的料场作业区最左端开始空机或载料运行,两者的速度之比为s：1（s ≥ 1）.决策者需确定储料堆在作业区的分布以及堆取料机处理它们的先后次序,目的是极小化一批煤料运输船的在港服务时间.考虑堆取料机处理完毕需要回到料场终端的作业模型,证明了存在最坏情况界不超过1+1/4s的近似算法.     

带约束的平行机排序的一个近似算法

讨论有资源约束和有机器准备时间的平行机排序问题,资源约束为每个机器至多可加工k个工件,在极小化makespan的上给出了一个匹配算法,证明其最坏情况最紧界是2-m^-1,并进一步给出了它的两个带参数的最坏情况界。     

可转包两台流水作业机排序的近似算法

研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为\frac{3}{2}的改进算法, 以上算法界均为紧界.     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

带机器准备时间的平行机ordinal排序及近似算法

本文研究带机器准备时间的m台平行机ordinal在线排序问题。讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法。对第一个目标，我们得到了3/2的下界和最坏情况界为2-1/m的近似算法。对第二个目标，我们得到了最坏情况为m的最好近似算法。我们还对一些特殊情况进行了分析。     

一类分式规划问题的ε-近似算法

本文针对一类复杂的分式规划问题,提出一种全局最优ε-近似解算法,并从理论上证明该算法的收敛性和计算复杂性,数值结果表明本文算法有效可行.     

一类广义分式规划问题的ε-近似算法

本文针对一类广义分式规划问题提出一种求其全局最优解的ε-近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值结果表明算法是有效可行的.     

一类特殊的分式规划问题的ε-近似算法

本文针对一类特殊的分式规划问题基于网格搜索提出了一个求其全局最优解的算法,且从理论上证明了算法的收敛性与计算复杂性,通过算例验证了算法的可行性与有效性.     

带有机器维修和两车辆派送的单机排序问题

研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型。不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的两辆同类车批次交付给单客户,目标函数是极小化最大完工时间,本文提出了2-近似算法,并证明了2是紧界。     

一类广义分式规划问题的完全多项式时间近似算法

本文对一类广义分式规划问题,提出一种求其全局最优解的完全多项式时间近似算法,给出该算法的理论分析和计算复杂性,通过数值算例验证该算法是有效可行的.     

A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time

For a container terminal system, efficient berth and quay crane (QC) schedules have great impact on the improvement of both operation efficiency and customer satisfaction. In this paper we address berth and quay crane scheduling problems in a simultaneous way, with uncertainties of vessel arrival time and container handling time. The berths are of discrete type and vessels arrive dynamically with different service priorities. QCs are allowed to move to other berths before finishing processing on currently assigned vessels, adding more flexibility to the terminal system. A mixed integer programming model is proposed, and a simulation based Genetic Algorithm (GA) search procedure is applied to generate robust berth and QC schedule proactively. Computational experiment shows the satisfied performance of our developed algorithm under uncertainty.     

Modeling and solution of the joint quay crane and truck scheduling problem

This paper addresses the joint quay crane and truck scheduling problem at a container terminal, considering the coordination of the two types of equipment to reduce their idle time between performing two successive tasks. For the unidirectional flow problem with only inbound containers, in which trucks go back to quayside without carrying outbound containers, a mixed-integer linear programming model is formulated to minimize the makespan. Several valid inequalities and a property of the optimal solutions for the problem are derived, and two lower bounds are obtained. An improved Particle Swarm Optimization (PSO) algorithm is then developed to solve this problem, in which a new velocity updating strategy is incorporated to improve the solution quality. For small sized problems, we have compared the solutions of the proposed PSO with the optimal solutions obtained by solving the model using the CPLEX software. The solutions of the proposed PSO for large sized problems are compared to the two lower bounds because CPLEX could not solve the problem optimally in reasonable time. For the more general situation considering both inbound and outbound containers, trucks may go back to quayside with outbound containers. The model is extended to handle this problem with bidirectional flow. Experiment shows that the improved PSO proposed in this paper is efficient to solve the joint quay crane and truck scheduling problem.     

An effective mathematical formulation for the unidirectional cluster-based quay crane scheduling problem

The quay crane scheduling problem plays an important role in the paradigm of port container terminal management, due to the fact that it closely relates to vessel berthing time. In this paper, we focus on the study of a special strategy for the cluster-based quay crane scheduling problem that forces quay cranes to move unidirectionally during the scheduling. The scheduling problem arising when this strategy is applied is called the unidirectional quay crane scheduling problem in the literature. Different from other researches attempting to construct more sophisticated searching algorithms, in this paper, we seek for a more compact mathematical formulation of the unidirectional cluster-based quay crane scheduling problem that can be easily solved by a standard optimization solver. To assess the performance of the proposed model, commonly accepted benchmark suites are used and the results indicate that the proposed model outperforms the state-of-the-art algorithms designed for the unidirectional cluster-based quay crane scheduling problem.     

集装箱码头桥机调度问题基于完工时间下界的算法

关注单船桥机调度问题,指出了单船桥机的闲置会影响码头整体的运作效率。以单个集装箱为任务单位,考虑桥机移动时间、安全距离等约束,建立了最小化桥机完工时间和闲置时间的多目标规划模型。基于完工时间下界的两种不同情况：以重点贝位工作量确定和以平均工作量确定,分别设计了基于邻域搜索的启发式算法和基于贪心策略的“分割贝位”算法,并且证明了在以平均工作量确定下界的情况中该算法不会导致桥机闲置。不同规模、不同下界类型的算例表明：提出的模型与算法得到的桥机调度计划更适合实际生产作业,能够有效地逼近完工时间下界,算法运行速度较现有的研究有显著的提高。     

目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法

本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。     

Improved 0/1-interchange scheduling

Consideration is given to the problem of nonpreemptively scheduling a set ofN independent tasks to a system ofM identical processors, with the objective to minimize the overall finish time. It is proved that the 0/1-INTERCHANGE scheduling heuristic can be modified, without increasing its time complexity fromO(N logM), so that its worst-case performance bound is reduced from 2 to 4/3 times optimal.     

有两个服务等级的平行机排序问题

对有两个服务等级的平行机排序问题的m台机情形,证明了修正的MF算法的最坏情况界不超过4/3 (1/2)~k,其中k是算法中预先给定的迭代次数.而已有的算法仅为2-1/(m-1),从而大大改进了已有文献中的结果.     

Approximation algorithms for scheduling unrelated parallel machines

We consider the following scheduling problem. There arem parallel machines andn independent jobs. Each job is to be assigned to one of the machines. The processing of jobj on machinei requires timep _ij . The objective is to find a schedule that minimizes the makespan.Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints.In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unlessP = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.A preliminary version of this paper appeared in theProceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science (Computer Society Press of the IEEE, Washington, D.C., 1987) pp. 217–224.