Using real options analysis to value reoptimization options in the shifting bottleneck heuristic

The reoptimization procedure within the shifting bottleneck (SB) involves reevaluation of all previously scheduled toolgroup subproblems at each iteration of the SB heuristic. A real options analysis (ROA) model is developed to value the option to reoptimize in the SB heuristic, such that reoptimization only occurs when it is most likely to lead to a schedule with a lower objective function. To date, all ROA models have sought to value options financially (i.e., in terms of monetary value). The ROA model developed in this paper is completely original in that it has absolutely no monetary basis. The ROA methodologies presented are shown to greatly outperform both full and no reoptimization approaches with respect to both computation time and total weighted tardiness. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Priority and dynamic scheduling in a make‐to‐stock queue with hyperexponential demand

We consider the scheduling problem in a make‐to‐stock queue with two demand classes that can be differentiated based on their variability. One class experiences Poisson arrivals and the other class experiences hyperexponential renewal arrivals. We provide an exact analysis of the case where the demand class with higher variability is given non‐preemptive priority. The results are then used to compare the inventory cost performance of three scheduling disciplines, first‐come first‐serve and priority to either class. We then build on an existing dynamic scheduling heuristic to propose a modification that works well for our system. Extensions of the heuristic to more than two classes and to the case where demand state is known are also discussed. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

支持多媒体应用的CPU调度模型

多媒体应用的出现对操作系统调度模型提出了新的要求，许多多媒体系统中既有硬、软实时应用程序，又有传统的分时应用程序，希望在同一操作系统框架内得到支持。本文提出了支持上述功能的ＣＰＵ调度模型，并设计了两种算法来实现该模型：基于ＱｏＳ的ＣＰＵ带宽划分算法和双优先级调度算法。     

Transshipment through crossdocks with inventory and time windows

A major challenge in making supply meet demand is to coordinate transshipments across the supply chain to reduce costs and increase service levels in the face of demand fluctuations, short lead times, warehouse limitations, and transportation and inventory costs. In particular, transshipment through crossdocks, where just‐in‐time objectives prevail, requires precise scheduling between suppliers, crossdocks, and customers. In this work, we study the transshipment problem with supplier and customer time windows where flow is constrained by transportation schedules and warehouse capacities. Transportation is provided by fixed or flexible schedules and lot‐sizing is dealt with through multiple shipments. We develop polynomial‐time algorithms or, otherwise, provide the complexity of the problems studied. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Disruption management in production planning

We study the problem of recovering a production plan after a disruption, where the disruption may be caused by incidents such as power failure, market change, machine breakdown, supply shortage, worker no‐show, and others. The new recovery plan we seek after has to not only suit the changed environment brought about by the disruption, but also be close to the initial plan so as not to cause too much customer unsatisfaction or inconvenience for current‐stage and downstream operations. For the general‐cost case, we propose a dynamic programming method for the problem. For the convex‐cost case, a general problem which involves both cost and demand disruptions can be solved by considering the cost disruption first and then the demand disruption. We find that a pure demand disruption is easy to handle; and for a pure cost disruption, we propose a greedy method which is provably efficient. Our computational studies also reveal insights that will be helpful to managing disruptions in production planning. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

On the asymptotic optimality of algorithms for the flow shop problem with release dates

We consider the nonpermutation flow shop problem with release dates, with the objective of minimizing the sum of the weighted completion times on the final machine. Since the problem is NP‐hard, we focus on the analysis of the performance of several approximation algorithms, all of which are related to the classical Weighted Shortest Processing Time Among Available Jobs heuristic. In particular, we perform a probabilistic analysis and prove that two online heuristics and one offline heuristic are asymptotically optimal. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

基于引擎成员的仿真调度问题

仿真引擎作为仿真系统的核心,是HLA仿真联邦中的特殊联邦成员。论述了基于实体、成员和引擎的层次式仿真调度概念结构,及其采用的基于时间序和事件序的仿真调度方案,将作战实体的时间推进和交战处理都归入仿真引擎,确保了全局时间统一性、实体同步性和交战事件的有序性,而且各种参量的设置灵活,便于控制。介绍了仿真引擎成员的设计与实现。该引擎成员在某指挥自动化作战效能仿真与评估系统中得以应用。     

高性能路由器中的分组非精确调度技术

随着网络带宽的不断提高,分组到达路由器的时间间隔不断缩短,对路由器处理分组的速度提出了新的要求。传统的分组调度算法,如WFQ,由于性能和可扩展性等问题,难以在高性能核心路由器中实现。为此,提出了分组非精确调度技术,在不影响应用QoS的前提下对经典的调度算法进行修改,通过简化硬件设计提高调度器的服务能力。模拟分析表明,采用非精确调度技术的SLQF算法的延时特性与传统算法LQF基本一致。     

Integrated scheduling of loading and transportation with tractors and semitrailers separated

Motivated by some practical applications, we study a new integrated loading and transportation scheduling problem. Given a set of jobs, a single crane is available to load jobs, one by one, onto semitrailers with a given capacity. Loaded semitrailers are assigned to tractors for transportation tasks. Subject to limited resources (crane, semitrailers, and tractors), the problem is to determine (1) an assignment of jobs to semitrailers for loading tasks, (2) a sequence for the crane to load jobs onto semitrailers, (3) an assignment of loaded semitrailers to tractors for transportation tasks, and (4) a transportation schedule of assigned tractors such that the completion time of the last transportation task is minimized. We first formulate the problem as a mixed integer linear programming model (MILPM) and prove that the problem is strongly NP‐hard. Then, optimality properties are provided which are useful in establishing an improved MILPM and designing solution algorithms. We develop a constructive heuristic, two LP‐based heuristics, and a recovering beam search heuristic to solve this problem. An improved procedure for solutions by heuristics is also presented. Furthermore, two branch‐and‐bound (B&B) algorithms with two different lower bounds are developed to solve the problem to optimality. Finally, computational experiments using both real data and randomly generated data demonstrate that our heuristics are highly efficient and effective. In terms of computational time and the number of instances solved to optimality in a time limit, the B&B algorithms are better than solving the MILPM. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 416–433, 2015     

基于空间约束的舰载机出库调度

舰载机在航母上的调度问题是制约舰载机出动和回收的重要因素,以往研究主要集中在飞行甲板调度方面。针对舰载机在航母上的出入库问题进行研究,着力解决舰载机在航母上二、三波次的出动能力。首先对舰载机出库的流程进行分析,梳理制约因素。其次,应用柔性流水车间调度理论对空间约束条件下的舰载机出库调度问题进行建模。再次,对智能粒子群算法应用于舰载机出库调度问题进行分析,对编码进行设计,并给出算法流程。最后,对出库流程进行仿真,计算出最优出库方案及时间,验证了模型的准确性。