一种改进的多模式项目反应性调度问题

既有的项目反应性调度问题只关注了基准调度方案的稳定性,而忽略了项目调度目标的最优实现。本文提出了一种两阶段多模式资源受限项目反应性调度问题。第一阶段,在新的项目执行环境下,对项目进行完全重调度,得到新的最优调度目标值。第二阶段,以新的最优调度目标值为约束,以最大化调度稳定性为目标,求得新的最优调度方案。针对问题特点,基于IBM ILOG优化编程语言OPL和CPLEX V12.8.0,设计出该问题的求解程序。最后,基于标准算例,对本文提出的反应性调度方法、既有的反应性调度方法、完全重调度方法进行了充分的比较测试,结果表明本文提出的反应性调度方法在缩短项目工期、保护基准方案的稳定性方面具有明显优势。     

Cargo ships routing and scheduling: Survey of models and problems

When a ship costs thousands of dollars per day, significant savings can be achieved by proper fleet routing and scheduling. In contrast to vehicle scheduling, relatively little work has been done in ship routing and scheduling. This paper discusses briefly the differences between vehicle and ship routing and scheduling and the reasons for the low attention to ship scheduling in the past. The various modes of operation of cargo ships are described and a classification scheme for ship routing and scheduling models and problems is proposed. A review of ship routing, scheduling and related models is provided. The review is broken down into the following categories: transportation system models, liner operations, tramp shipping, industrial operations and other models. Finally, recent trends in ship scheduling, shortcomings in existing models and requirements from realistic models are discussed.     

具有学习-遗忘效应的半导体批调度问题研究

半导体生产制造系统具有大规模、工艺繁杂、随机性大、可重入等显著特点。以半导体最终测试阶段批处理调度为基础,把学习-遗忘效应应用到典型半导体批调度问题中,构建基于学习-遗忘效应的批调度模型。分别结合调度问题和调度模型对双层算法(粒子群算法&萤火虫算法)进行设计,通过仿真实验检验了双层算法在求解具有学习遗忘效应的批调度模型方面的可行性和有效性,并对比分析以最大完工时间为优化目标的实验结果,探讨学习遗忘效应对半导体批调度问题的影响程度,对实际半导体生产具有重要指导意义。     

实时系统中单处理器调度算法的优化设计研究

研究实时系统的建模与调度问题是运筹与控制领域研究的热点问题, 对实时系统中的单处理器的调度算法进行了分析与研究, 特别是对其中的单调速率算法和最早时间限优先算法进行了深入的研究, 指出单调速率算法是一种典型的静态调度算法, 并且证明了单调速率算法是单处理器最优的静态优先级调度算法, 同时还指出最早时间限优先算法是一种典型的动态优先级调度算法,证明了最早时间限优先算法是单处理器的最优的动态优先级调度算法. 最后, 为了更好地进行实时系统的建模与调度, 引入了一种新的对任务执行行为进行抽象的方法--T-LET平面方法, 利用这种方法建立了单处理器流调度模型和BLREF调度算法, 并指出这种模型和算法都具有很强的几何背景.     

NP-hardness of compact scheduling in simplified open and flow shops

In practical task scheduling it is sometimes required that the components of a system perform consecutively. Such a scheduling is called scheduling without waiting periods or no-wait and/or no-idle. In this article we study the complexity of some simplified scheduling problems of this kind in open shop and flow shop settings. In particular, we show that many trivial questions about the existence of schedule become NP-hard, even if there are only two machines or if the scheduling graph of a system is a path or a cycle.     

协同设计资源的两级不确定调度问题研究及其求解

针对协同设计资源调度问题中存在的设计任务不确定、资源需求模糊以及任务进行过程中可能出现变化等情况,提出一种基于不确定规划和反应式调度的两级不确定调度模型,通过根据满足系数对最好及最坏规划进行折中的方法对模型进行转化,然后采用离散的自由搜索算法进行求解.通过实例,验证了该方法的有效性.     

Isomorphic scheduling problems

We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.     

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.     

小批量随机块坐标下降算法

针对机器学习中广泛存在的一类问题：结构化随机优化问题（其中“结构化”是指问题的可行域具有块状结构,且目标函数的非光滑正则化部分在变量块之间是可分离的）,我们研究了小批量随机块坐标下降算法（mSBD）。按照求解非复合问题和复合问题分别给出了基本的mSBD和它的变体,对于非复合问题,分析了算法在没有一致有界梯度方差假设情况下的收敛性质。而对于复合问题,在不需要通常的Lipschitz梯度连续性假设条件下得到了算法的收敛性。最后通过数值实验验证了mSBD的有效性。     

Tri-directional Scheduling Scheme: Theory and Computation

In this paper we introduce a new scheduling scheme based on so called tri-directional scheduling strategy to solve the well known resource constrained project scheduling problem. In order to demonstrate the effectiveness of tri-directional scheduling scheme, it is incorporated into a priority rule based parallel scheduling scheme. Theoretical and numerical investigations show that the tri-directional scheduling scheme outperforms forward, backward and even bidirectional schemes depending on the problem structure and the priority rule used. Based on empirical evidence, it seems that as the number of activities are increased, the tri-directional scheduling scheme performs better irrespective of the priority rule used. This suggests that tri-directional scheme should also be applied within the category of heuristic methods.     

A pattern-directed approach to FMS scheduling

Scheduling in flexible manufacturing systems (FMS) must take into account the shorter lead time, the multiprocessing environment, and the dynamically changing states. In this paper, a pattern-directed approach is presented which incorporates a nonlinear planning method developed in the artificial intelligence field. The scheduling system described here is knowledge-based and utilizes both forward-and backward-chaining for generating schedules (treated as state-space plans). The pattern-directed approach is dynamically adjustable and thus can handle scheduling requirements unique to the FMS environment, such as dynamic scheduling, failure-recovery scheduling, or prioritized scheduling for meeting deadlines.     

Scheduling coordination problems in supply chain planning

Scheduling algorithms and their role in supply chain planning are topics that have been discussed in scheduling literature for many years. Based on examples and experience with commercial supply chain planning software, this paper presents background information about production planning and scheduling functionality in commercial supply chain planning software and interesting scheduling coordination problems in supply chain planning for researchers. We first provide an overview of different planning activities in supply chain planning, while taking into consideration existing functionalities that are available in commercial supply chain planning software. As a second step, we show three scheduling coordination problems in supply chain planning, namely the integration of production planning and production scheduling, the integration of sales order confirmation and production scheduling and the integration of VMI planning and production scheduling. We conclude this paper with a detailed discussion of an implementation of a supply chain planning solution at the tissue producer SCA Hygiene in Sweden. This paper expresses the authors opinion and does not represent an official statement from SAP.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

Greedy scheduling with custom-made objectives

We present a methodology to automatically generate an online job scheduling method for a custom-made objective and real workloads. The scheduling problem comprises independent parallel jobs and parallel identical machines and occurs in Massively Parallel Processing systems and computational Grids. The system administrator defines the scheduling objective that may consider job properties and priorities of users or user groups. Our scheduling method combines a Greedy scheduling algorithm with the dynamic sorting of the waiting queue. This sorting algorithm uses a criterion that is modifiable by a set of parameters. Finding good parameter settings for the sorting criterion is viewed as a nonlinear optimization problem which is solved with the help of Evolution Strategies. We evaluate our scheduling method with real workload data and compare it to approximated optimal offline solutions and to the online results of the standard EASY backfill algorithm.     

A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis

In this note we propose an iterative scheduling technique which consists of consecutive forward/backward scheduling passes aimed at reducing the project duration by smoothing out the project's resource profile. The idea of iterative scheduling is initiated by Li and Willis in their related paper. The only common point between their scheduling technique and the one proposed here is the iterative feature. The two techniques differ both in algorithmic aspects and in the way activities are selected for scheduling at a decision point. In the technique proposed here activities are evaluated by well-reputed dispatching rules and a conflict based decision-making process called Local Constraint Based Analysis (LCBA). The results on benchmark problems from the literature demonstrate that LCBA specifically exploits the flexible activity time windows provided by the iterative scheduling technique.     

Multi-level lotsizing and scheduling by batch sequencing

We consider a single-machine scheduling problem with a multi-level product structure. Setups are required if the machine changes production from one product type to another, and the scheduling decision must satisfy dynamic demand. We propose a lotsizing as well as a scheduling model, and we compare solution procedures for both models on a very restricted set of instances. As a result the multi-level structure complicates the inventory balance constraints in the lotsizing model. In the scheduling model, however, the multi-level structure translates into precedence constraints between jobs (leading to a smaller search space) which allows it to solve the scheduling model to optimality.     

The project scheduling problem with production and consumption of resources: A list-scheduling based algorithm

The paper deals with algorithms for applying classical list scheduling to a project scheduling problem where the units of resources are produced or consumed at the occurrence of precedence-related events. It is shown that the feasibility variant of the project scheduling problem is NP-complete. Moreover, polynomial-time scheduling algorithms are devised for the three cases where the occurrence time sequence of all events or the consuming events or the producing events is given in advance. By enumerating these sequences (called linear orders), one obtains a list-scheduling based algorithm for minimizing the makespan of a project scheduling problem with production and consumption of resources.     

Optimal fuzzy counterparts of scheduling rules

The optimality of a fuzzy logic alternative to the usual treatment of uncertainties in a scheduling system using probability theory is examined formally. Fuzzy scheduling techniques proposed in the literature either fuzzify directly the existing scheduling rules, or solve mathematical programming problems to determine the optimal schedules. In the former method, the fuzzy optimality for the optimal scheduling rules is usually not justified but still assumed. In this paper, the necessary conditions for fuzzy optimality are defined, and fuzzy counterparts of some of the well-known scheduling rules such as shortest processing time (SPT) and earliest due date (EDD) are developed.     

Constraint-Based Job Shop Scheduling with IILOG SCHEDULER

We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.     

New trends in machine scheduling

This review is concerned with new directions in deterministic machine scheduling theory. We study: resource constrained scheduling, scheduling tasks that require more than one machine at a time, scheduling with nonlinear speed-resource alloted functions, and scheduling in flexible manufacturing systems. The two features that distinguish the above problems are the use of resources in addition to the machines and new models for the processing of tasks. The study of these models was primarily motivated by their practical importance. In each case, we overview the existing results and present solution strategies for particularly chosen problems.