Integrating planning and scheduling

Planning and scheduling research is becoming an increasingly interesting topic in the artificial intelligence area because of its immediate application to real problems. Although the last few years have seen dramatic advances in planning systems, they have not seen the same advances in the methods of solving planning and scheduling problems. In this paper, an intuitive way of integrating independent planning and scheduling processes is presented which achieves better performance in the process of solving planning and scheduling problems. The integrated system has the advantage of obtaining a final plan that is executable and optimal. Moreover, the system discards any partial plan as soon as the plan becomes invalid, improving its performance. Experience demonstrates the validity of this system for tackling planning and scheduling problems.     

Collision-free motion planning and scheduling

The positioning, motion coordination and test ordering procedures of new testing equipment for printed circuit boards is presented. The equipment structure consists of four mobile probes whose movements must be coordinated to avoid collisions both with obstacles and with each other. This paper explains the algorithm used to obtain the optimum path between two points in a space with obstacles based on traditional methods but including new ideas to reduce the computation times. A new method for motion coordination that obtains the optimum sequence of consecutive or simultaneous probe movements is also introduced and is based on the decomposition of the sequence of movements into stages in which only movements without interferences are permitted. Finally, the ordering of the tests can be viewed as a traveling salesman problem, and the paper presents the results of various methods when applied to the specific characteristics of the equipment involved.     

Verification and validation of knowledge-based systems

Knowledge-based systems (KBSs) are being used in many applications areas where their failures can be costly because of losses in services, property or even life. To ensure their reliability and dependability, it is therefore important that these systems are verified and validated before they are deployed. This paper provides perspectives on issues and problems that impact the verification and validation (V&V) of KBSs. Some of the reasons why V&V of KBSs is difficult are presented. The paper also provides an overview of different techniques and tools that have been developed for performing V&V activities. Finally, some of the research issues that are relevant for future work in this field are discussed     

Verification and validation of Bayesian knowledge-bases

Knowledge-base V&V primarily addresses the question: “Does my knowledge-base contain the right answer and can I arrive at it?” One of the main goals of our work is to properly encapsulate the knowledge representation and allow the expert to work with manageable-sized chunks of the knowledge-base. This work develops a new methodology for the verification and validation of Bayesian knowledge-bases that assists in constructing and testing such knowledge-bases. Assistance takes the form of ensuring that the knowledge is syntactically correct, correcting “imperfect” knowledge, and also identifying when the current knowledge-base is insufficient as well as suggesting ways to resolve this insufficiency. The basis of our approach is the use of probabilistic network models of knowledge. This provides a framework for formally defining and working on the problems of uncertainty in the knowledge-base.

In this paper, we examine the project which is concerned with assisting a human expert to build knowledge-based systems under uncertainty. We focus on how verification and validation are currently achieved in .     

OVA技术在接口时序验证中的应用

本文主要阐述了基于断言技术并结合动态仿真,形式测试,测试激励自动化等方法的新硬件验证平台,着重介绍了OVA的特点及运用,并以LCD controller的sharp接口为实例讲解了该方法的优点.     

Verification and validation of an intelligent tutorial system

This paper presents the results of a verification and validation process for an intelligent system. The system being studied is an Intelligent Tutorial that employs fuzzy logic and multiagent systems. Software engineering techniques were used in the verification process, while the validation exploited both qualitative and quantitative techniques.     

Constraint satisfaction techniques in planning and scheduling

Over the last few years constraint satisfaction, planning, and scheduling have received increased attention, and substantial effort has been invested in exploiting constraint satisfaction techniques when solving real life planning and scheduling problems. Constraint satisfaction is the process of finding a solution to a set of constraints. Planning is the process of finding a sequence of actions that transfer the world from some initial state to a desired state. Scheduling is the problem of assigning a set of tasks to a set of resources subject to a set of constraints. In this paper, we introduce the main definitions and techniques of constraint satisfaction, planning and scheduling from the Artificial Intelligence point of view.     

A featured-based dynamic process planning and scheduling

The paper presents a dynamic featured-based process planning and scheduling system which is currently under development utilizing a commercial CAD system.

In this system, the product features are extracted using an AI-based feature extractor according to the shop floor capabilities. Using this system, the products can be dynamically process planned and scheduled.     

Integration of process planning and scheduling functions

Automated process planning (APP) has received a considerable amount of attention in recent years. This has mainly been due to APP allowing for the bridging of the gap between design and manufacturing, and for its automation of the related tedious human task. While there have been several efforts in developing interfaces between computer-aided design (CAD) and APP, little attention has been given to the integration of APP and scheduling, which is likely to be of even higher importance. This paper addresses the basic issues involved in the integration of the two functions, demonstrates a methodology and the potential benefits of the integrated approach by an example, and presents directions for future research.     

Acquisition planning and scheduling of computing resources

Cloud computing has been attracting considerable attention since the last decade. This study considers a decision problem formulated from the use of computing services over the Internet. An agent receives orders of computing tasks from his/her clients and on the other hand he/she acquires computing resources from computing service providers to fulfill the requirements of the clients. The processors are bundled as packages according to their speeds and the business strategies of the providers. The packages are rated at a certain pricing scheme to provide flexible purchasing options to the agent. The decision of the agent is to select the packages which can be acquired from the service providers and then schedule the tasks of the clients onto the processors of the acquired packages such that the total cost, including acquisition cost and scheduling cost (total weighted tardiness), is minimized. In this study, we present an integer programming model to formulate the problem and propose several solution methods to produce acquisition and scheduling plans. Ten well-known heuristics of parallel-machine scheduling are adapted to fit into the studied problem so as to provide initial solutions. Tabu search and genetic algorithm are tailored to reflect the problem nature for improving upon the initial solutions. We conduct a series of computational experiments to evaluate the effectiveness and efficiency of all the proposed algorithms. The results of the numerical experiments reveal that the proposed tabu search and genetic algorithm can attain significant improvements.     

Constraint satisfaction for planning and scheduling problems

The areas of planning and scheduling (from the Artificial Intelligence point of view) have seen important advances thanks to application of constraint satisfaction techniques. Currently, many important real-world problems require efficient constraint handling for planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Solutions to these problems require integration of resource allocation and plan synthesis capabilities. Hence to manage such complex problems planning, scheduling and constraint satisfaction must be interrelated. This special issue on Constraint Satisfaction for Planning and Scheduling Problems compiles a selection of papers dealing with various aspects of applying constraint satisfaction techniques in planning and scheduling. The core of submitted papers was formed by the extended versions of papers presented at COPLAS??2009: ICAPS 2009 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research.     

进程调度模型的Spin验证分析与改进

Spin不仅可以用于通信协议的正确性验证,也可以对其进行有效的安全性分析.对用Promela语言描述的进程调度模型进行分析研究,并对其存在的不足加以改进.增加了LTL式描述,用spin进行模型检测验证,使用Xspin得到了反例状态迁移轨迹图.     

Production planning & scheduling: Computational feasibility of multi-criteria models of production, planning and scheduling

This paper surveys the applications of multi-criteria decision making (MCDM) methods to production planning, scheduling, and sequencing problems. The basic structure of the decision models are described by their objectives and the resulting models are classified by decision variables into the areas of Aggregate Production Planning, Disaggregate Production Planning, Production Scheduling, and Single Machine Sequencing. The problem sizes that have been solved are summarized to determine how practical it is to use MCDM.     

军事训练游戏关卡设计校核与验证

针对军事训练游戏关卡设计校核与验证问题,分析了军事训练游戏关卡设计流程,研究了军事训练游戏关卡设计文档需要校核与验证的内容,提出了军事训练游戏关卡设计校核与验证的五项指标以及军事训练游戏关卡设计校核与验证实施步骤。研究的内容对军事训练游戏关卡设计的校核与验证工作具有很好的指导作用,军事训练游戏项目管理人员可以参考提出的校核与验证内容、指标、步骤组织实施关卡设计校核与验证。     

Verification and validation of declarative model-to-model transformations through invariants

In this paper we propose a method to derive OCL invariants from declarative model-to-model transformations in order to enable their verification and analysis. For this purpose we have defined a number of invariant-based verification properties which provide increasing degrees of confidence about transformation correctness, such as whether a rule (or the whole transformation) is satisfiable by some model, executable or total. We also provide some heuristics for generating meaningful scenarios that can be used to semi-automatically validate the transformations.As a proof of concept, the method is instantiated for two prominent model-to-model transformation languages: Triple Graph Grammars and QVT.     

Introduction to planning, scheduling and constraint satisfaction

Planning, scheduling and constraint satisfaction are important areas in artificial intelligence (AI). Many real-world problems are known as AI planning and scheduling problems, where resources must be allocated so as to optimize overall performance objectives. Therefore, solving these problems requires an adequate mixture of planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Constraint satisfaction plays also an important role to solve real-life problems, so that integrated techniques that manage planning and scheduling with constraint satisfaction remains necessary. This special issue on Planning, Scheduling and Constraint Satisfaction compiles a selection of papers of CAEPIA’2007 workshop on Planning, Scheduling and Constraint Satisfaction and COPLAS’2007: CP/ICAPS 2007 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research. Furthermore, this issue also includes a complete survey about constraint satisfaction, planning, scheduling and integration among these areas.     

Project-driven planning and scheduling support for virtual manufacturing

The paper addresses the issue of decision-making support for small and medium-size enterprises operating within a virtual project-driven enterprise environment. The problem considered here can be defined in terms of finding a feasible schedule that satisfies the constraints imposed by the work-order duration, the price, and the time-constrained resource availability. The problem belongs to the class of multi-mode case problems of project scheduling, where finding a feasible solution is NP-hard. A heuristic method for process planning and scheduling is proposed. The method is based on a critical path approach and the branch and bound search scheme. It has been implemented in a web-enabled interactive software package, and is illustrated using the example of a virtual construction enterprise. Received: February 2005 / Accepted: January 2006