自动化码头双小车岸桥与AGV协调调度问题研究

为研究自动化集装箱码头中自动导引运输车（Automated Guided Vehicle，AGV）与双小车岸桥（Double-Trolley Quay Crane，QC）的协调调度问题，考虑双小车岸桥中转平台及其容量限制，并以双小车岸桥门架小车时间窗为约束，建立以集装箱任务最大完工时间最小化为目标的混合整数规划模型。设计启发式算法，由中转平台的容量求得岸桥门架小车操作集装箱任务的时间窗，并采用遗传算法进行求解，给出相应的AGV调度优化方案，解决两大设备的协调调度问题。最后，以10组实验为例，比较了遗传算法与粒子群算法的优化结果。结果表明两种算法一致，且基于遗传算法的模型求解收敛速度更快，从而验证了该算法的可行性。     

考虑作业状态能耗的集装箱码头设备协调调度

绿色港口日渐成为港口发展的必然趋势,为了提高集装箱码头的服务水平及降低其能耗,综合分析了集装箱码头的装卸作业流程,考虑岸桥、场桥、集卡在不同作业状态下的能耗,且以总完工时间和总作业能耗最小为目标建立了多目标混合整数规划模型。使用MATLAB编码改进自适应遗传算法求解所建模型,并分别与CPLEX和原始遗传算法的求解结果作对比,证明了该算法的优秀性。更改能耗目标和作业时间目标所占权重进行求解,发现考虑各设备在不同作业状态下的能耗会影响总完工时间,且能耗与作业时间是相互冲突的目标,追求低能耗会造成作业效率的牺牲。分析结果表明,所建模型和算法在岸桥、场桥和集卡的协调调度问题中可以帮助决策者更好地权衡作业时间和能耗目标。     

基于GA-PSO的天基预警系统资源调度方法

为解决天基预警系统中的卫星资源调度问题,从预警任务特点出发,在对预警任务进行分解的基础上,建立了资源调度模型．结合传统遗传算法（GA）和粒子群算法（PSO）的优点,采用一种混合遗传粒子群（GA-PSO）算法来求解资源调度问题．该算法在解决粒子编解码问题的前提下,将遗传算法的遗传算子应用于粒子群算法,改善了粒子群算法的寻优能力．实验结果表明,提出的算法能有效解决多目标探测时天基预警系统的资源调度问题,调度结果优于传统粒子群算法和遗传算法．     

不确定环境下码头堆场设备集成调度优化

集装箱码头堆场设备调度优化中,对确定条件下的内集卡和场桥的联合调度研究较多,且没有考虑外集卡的随机到达情况。考虑内集卡和场桥作业过程中的不确定性因素,包括：内集卡行驶速度,场桥行走速度和作业时间,并考虑外集卡随机到达堆场对于内集卡调度作业的影响,构建了不确定因素条件下的堆场设备集成调度优化模型,其优化目标是在考虑外集卡随机到达的情况下,最优化堆场设备的作业时间。设计了求解模型的粒子群算法,并比较了一般确定性模型和考虑不确定因素优化模型的结果。算例结果表明,所建立的模型和算法能有效真实地反映不确定因素对集装箱码头堆场设备作业的影响。     

干扰约束下考虑分组作业面的岸桥AGV联合调度

为解决自动化码头海侧多阶段设备作业的协调问题,加快集装箱在码头内部的周转过程。考虑干扰约束下分组作业面的的岸桥自动导引小车（AGV）联合调度问题。以岸桥、AGV完工时间和AGV等待时间加权总和最小为目标,考虑岸桥实际操作中的干扰约束与AGV堵塞等待等情况,建立岸桥与AGV联合调度优化模型。提出岸桥动态调度与AGV分组作业面调度模式,设计不同规模的算例,并采用遗传算法（GA）进行求解,将计算结果与传统调度模式进行对比。结果表明,该算法能有效提高岸桥与AGV作业效率,降低AGV的等待时间与堵塞次数,为码头实际作业提供依据。     

考虑能耗节约的集装箱码头双小车岸桥与AGV联合配置及调度优化

合理调度集装箱码头的装卸设备以减少生产过程中的能耗, 对实现其低碳绿色化发展具有重要意义. 针对集装箱码头向自动化发展过程中的双小车岸桥与AGV (Automated guided vehicle)联合配置及调度问题, 考虑AGV续航时间、双小车岸桥中转平台容量和堆场缓冲支架容量约束, 以岸桥的能耗最小为第一阶段模型的优化目标, 以AGV运输过程的能耗最小为第二阶段目标建立两阶段优化模型; 设计枚举法求解第一阶段模型, 改进遗传算法求解第二阶段优化模型. 以洋山四期自动化集装箱码头为例进行实验分析, 针对不同船舶在港总装卸时间和AGV配置原则进行实验, 验证了模型和算法的有效性, 结果表明以最小化能耗为目标的双小车岸桥与AGV联合调度可在岸桥主小车不延误的前提下, 显著减少AGV的配置数量.     

GA与PSO解DE与LP问题的效率比较

遗传算法和粒子群算法都具有很强的搜索能力,在最优化问题中有着极其广泛的应用.文章针对常微分方程(DE)近似解和一般线性规划(LP)问题的解利用遗传算法和粒子群算法求解,深入的比较和分析了GA与PSO在这两种优化问题中的效率.在固定其他参数而调整群体数量的基础上比较了GA与PSO在微分方程近似解和LP问题解的优化能力.     

面向端元提取的粒子群优化遗传算法

现有的粒子群优化(PSO)算法和遗传算法(GA)无法很好地解决高光谱影像端元提取这类离散解空间内的大规模取样优化问题。针对该问题,借鉴凸面几何学理论,利用局部模式粒子群优化的原理改进遗传算法,提出一种面向高光谱影像端元提取的粒子群优化遗传算法(PSOGA)。利用模拟数据和PHI影像对PSOGA算法和GA算法进行实验对比。分析结果证明,PSOGA算法的收敛速度优于GA算法。     

考虑集装箱簇边装边卸的港口集卡调度模型求解

文章在集装箱装卸作业问题中,以集装箱簇为作业单位,分两阶段分析集装箱在岸桥集卡间的调度方案,以集卡空驶率最小与移动距离最短为目标,建立了整数规划模型。针对上述模型,文章利用启发式算法与自适应遗传算法对问题进行分析求解。最后通过配置不同集卡数量,将其移动总距离以及空驶效率进行比较,并与禁忌搜索算法相对比。试验结果表明,启发式自适应遗传算法的计算结果在空驶率以及移动总距离最小问题上有更优的解决方案。     

混堆模式下基于动态规则NSGAⅡ的自动堆垛起重机作业优化

针对外集卡到达时间的不确定性,提出自动堆垛起重机（ASC）作业序列的动态优化,从而以减少ASC作业完成时间以及ASC和外集卡等待时间为目的,提高自动化集装箱码头堆场的作业效率。首先,结合混堆模式下集装箱作业类型与外集卡动态到达的特点,提出ASC动态匹配外集卡作业任务的策略;其次,构建ASC作业时间最短与ASC和外集卡等待时间最短的多目标模型;最后,设计基于动态规则的非支配排序遗传算法Ⅱ（DRNSGAⅡ）作为求解算法。在小规模算例实验中,分别运用DRNSGAⅡ与遗传算法（GA）求解动态策略和随机策略下的ASC作业问题。实验结果表明,DRNSGAⅡ求解的动态策略下目标函数值优于随机策略28.2%,并且动态策略下DRNSGAⅡ的求解结果优于遗传算法23.3%。在大规模算例实验中,比较了DRNSGAⅡ与多目标粒子群优化（MOPSO）两种算法的性能。实验结果表明DRNSGAⅡ的求解结果优于MOPSO算法6.7%。可见DRNSGAⅡ能够快速生成多样化的非支配解,为混堆模式下的ASC动态作业提供决策支持。     

实时系统调度算法综述

在多道程序环境下,主存中有多个进程,其数目往往多于处理机数目。操作系统通过处理机调度程序,按照某种调度算法动态地把处理机分配给就绪队列中的一个进程,使之执行。处理机是重要的计算机资源,提高处理机的利用率及改善系统性能（吞吐量、响应时间）,很大程度上取决于处理机调度性能的好坏,因而操作系统的调度算法是非常重要的。通过研究基本的操作系统作业（进程）调度算法,详尽分析和对比这些调度算法的优势和劣势。最后对新兴的实时系统研究现状进行介绍和展望,为以后实时系统调度算法研究提供了有效的参考价值。     

Reactive scheduling in the multi-mode RCPSP

The multi-mode resource-constrained project scheduling problem (MRCPSP) involves the determination of a baseline schedule of the project activities, which can be executed in multiple modes, satisfying the precedence relations and resource constraints while minimizing the project duration. During the execution of the project, the baseline schedule may become infeasible due to activity duration and resource disruptions. We propose and evaluate a number of dedicated exact reactive scheduling procedures as well as a tabu search heuristic for repairing a disrupted schedule, under the assumption that no activity can be started before its baseline starting time. We report on promising computational results obtained on a set of benchmark problems.     

The impact of reserve duties on the robustness of a personnel shift roster: An empirical investigation

In personnel scheduling, a duty roster is typically constructed under the assumption of a deterministic model. However, organisations operate in a stochastic environment and the conjectures made about the demand for staff and the availability of employees may prove to be insufficient to represent reality. In order to anticipate these unexpected events, we investigate the impact of introducing reserve duties in the medium-term personnel shift roster. Reserve duties are scheduled by enforcing specific staffing requirements and/or time-related constraints that consider reserve duties only. We propose a three-step methodology that imitates the workforce management process to evaluate the delivered robustness in terms of the actual performance. After a personnel roster is constructed, unexpected events are simulated and an optimisation model determines the required adjustments to balance supply and demand. Detailed computational experiments are presented to provide managerial insights into different strategies to schedule reserve duties.     

元计算环境中任务调度的深入分析

文章主要对元计算环境中任务调度进行了深入分析与研究。先概述了元计算系统对于科学领域的贡献,分析了元计算环境的特点;然后对元计算环境中的调度算法进行了分类说明,并对几种典型的调度算法行了具体的分析,评价了其特点与不足之处;最后分析了新兴的元计算环境—校园级元计算环境面临的挑战,借鉴各种调度算法,提出了与之相适应的任务调度策略,对其可行性进行了分析,并简要概括了其创新性。     

Cut scheduling in the apparel industry

A problem encountered in the apparel industry is that of producing, with no excess, a known number of different styles from the same cloth. This situation occurs, for instance, in the case of special order or made-to-order garments. In the cutting process, plies of cloth are spread on a cutting table, and several patterns are placed across the top ply. Cutting out the patterns through all plies creates a set of bundles of garment pieces, and several such lays may be required to satisfy all demands. The cut scheduling problem concerns finding a feasible cutting schedule having the minimum number of lays. We present an exact enumerative approach that identifies all optimal solutions to a practically important variant of this problem. The availability of multiple solutions allows greater flexibility and permits decision makers to apply additional criteria in selecting an appropriate cutting schedule. Computational evidence shows that our approach can efficiently solve standard test problems from the literature as well as some very challenging examples provided by a global garment manufacturer.     

Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation

This paper presents an applied study of scheduling buses and drivers for the Beijing Bus Group (BJBUS), the largest bus company in China. This is pioneering research in China for bus transit scheduling using computers based on a unified mode of operation. It is anticipated that the research fruits and experiences obtained would be of benefit to other bus operators in China. The bus transit scheduling problem in BJBUS is first presented in the paper. The particular characteristics are pointed out, which are different from those in developed countries, while many are common in China. After a brief review and analysis of the appropriateness of some currently successful approaches, the paper focuses on reporting the solution ideas and methods for BJBUS, especially those developed to solve the specific problems of BJBUS, such as scheduling buses with built-in meal periods, multi-type bus scheduling, restricting drivers to one or two particular buses, etc. Finally, the implementation and computational results are reported before the concluding remarks.     

A survey of dynamic scheduling in manufacturing systems

In most real-world environments, scheduling is an ongoing reactive process where the presence of a variety of unexpected disruptions is usually inevitable, and continually forces reconsideration and revision of pre-established schedules. Many of the approaches developed to solve the problem of static scheduling are often impractical in real-world environments, and the near-optimal schedules with respect to the estimated data may become obsolete when they are released to the shop floor. This paper outlines the limitations of the static approaches to scheduling in the presence of real-time information and presents a number of issues that have come up in recent years on dynamic scheduling. The paper defines the problem of dynamic scheduling and provides a review of the state-of-the-art of currently developing research on dynamic scheduling. The principles of several dynamic scheduling techniques, namely, heuristics, meta-heuristics, multi-agent systems, and other artificial intelligence techniques are described in detail, followed by a discussion and comparison of their potential.     

Development of scheduling strategies in the TITAN operating system

Scheduling strategies are evolved to solve problems of selection in operating systems. Such strategies frequently undergo evolution in time as details of the specification are changed or, more frequently, as inadequacies in them are shown up by use in a heavily loaded system. This paper describes a number of scheduling strategies used in the TITAN system, and their development to meet changing circumstances or to overcome inadequacies.     

Product-based and resource-based heterarchical approaches for dynamic FMS scheduling

Two fundamental approaches can be adopted for heterarchical scheduling of flexible manufacturing systems: resource-based scheduling or product-based scheduling. The first part of this paper defines the basic concepts of these two methods (modeling, structure design methodology, communication protocols). The second describes the specific advantages and drawbacks of these two approaches using the results provided to illustrate the discussion. The final section considers a real implementation of the product-based heterarchical philosophy.     

Achieving Efficiency and Accuracy in the ALPS Application-level Proportional-share Scheduler

We present the design and implementation of ALPS, a per-application user-level proportional-share scheduler. It provides an application with a way to control the relative allocation of CPU time amongst its individual processes. The ALPS scheduler runs as just another process (belonging to the application) at user level; thus, it does not require any special kernel support, nor does it require any special privileges, making it highly portable. To achieve efficiency, ALPS delegates fine-grained time-slicing responsibility to the underlying kernel scheduler, while itself making coarse-grained decisions to achieve proportional-share scheduling, all in a way that is transparent to the underlying kernel. Our results show that the ALPS approach is practical; we can achieve good accuracy (under 5% relative error) and low overhead (under 1% of CPU time), despite user-level operation.