Exact and heuristic algorithms for the aerial refueling parallel machine scheduling problem with due date-to-deadline window and ready times

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for fighter aircrafts (jobs) on multiple tankers (machines) to minimize the total weighted tardiness. ARSP can be modeled as a parallel machine scheduling with ready times and due date-to-deadline window to minimize total weighted tardiness. ARSP assumes that the jobs have different ready times and a due date-to-deadline window between refueling due date and a deadline to return without refueling. In this paper, we first formulate the ARSP as a mixed integer programming model. The objective function is a piece-wise tardiness cost that takes into account due date-to-deadline windows and job priorities. Since ARSP is NP-hard, two heuristics are proposed to obtain solutions in reasonable computation times, namely (1) modified ATC rule (MATC), (2) a simulated annealing method (SA). The proposed heuristic algorithms are tested in terms of solution quality and CPU time through computational experiments with data randomly generated to represent aerial refueling operations of an in-theater air operation. Solutions provided by both algorithms were compared to optimal solutions for problems with up to 12 jobs and to each other for larger problems with up to 60 jobs. The results show that, MATC is more likely to outperform SA especially when the problem size increases, although it has significantly worse performance than SA in terms of deviation from optimal solution for small size problems. Moreover CPU time performance of MATC is significantly better than SA in both cases.     

Compiler-assisted energy optimization for clustered VLIW processors

Clustered architecture processors are preferred for embedded systems because centralized register file architectures scale poorly in terms of clock rate, chip area, and power consumption. Although clustering helps by improving the clock speed, reducing the energy consumption of the logic, and making the design simpler, it introduces extra overheads by way of inter-cluster communication. This communication happens over long global wires having high load capacitance which leads to delay in execution and significantly high energy consumption. Inter-cluster communication also introduces many short idle cycles, thereby significantly increasing the overall leakage energy consumption in the functional units. The trend towards miniaturization of devices (and associated reduction in threshold voltage) makes energy consumption in interconnects and functional units even worse, and limits the usability of clustered architectures in smaller technologies. However, technological advancements now permit the design of interconnects and functional units with varying performance and power modes. In this paper, we propose scheduling algorithms that aggregate the scheduling slack of instructions and communication slack of data values to exploit the low-power modes of functional units and interconnects. Finally, we present a synergistic combination of these algorithms that simultaneously saves energy in functional units and interconnects to improves the usability of clustered architectures by achieving better overall energy–performance trade-offs. Even with conservative estimates of the contribution of the functional units and interconnects to the overall processor energy consumption, the proposed combined scheme obtains on average 8% and 10% improvement in overall energy–delay product with 3.5% and 2% performance degradation for a 2-clustered and a 4-clustered machine, respectively. We present a detailed experimental evaluation of the proposed schemes. Our test bed uses the Trimaran compiler infrastructure.     

Solving multiple processor and multiple resource constrained scheduling problems using a genetic algorithm approach

We consider the multiprocessor scheduling of unit time tasks with precedence constraints and finite set of limited resources. Each task demands some amount of resources for its execution and the total demand for each kind of resources must not exceed a certain limit at any instant of time. Our objective is to find out the minimum time schedule which satisfies the partial orders and the resource usage constraints. We have applied Genetic Algorithm for the present problem. We have shown that the Genetic Algorithm is quite superior to the First Fit Decreasing method.     

A task‐based and resource‐aware approach to dynamically generate optimal software architecture for intelligent service robots

Intelligent service robots provide various services to users by understanding the context and goals of a user task. In order to provide more reliable services, intelligent service robots need to consider various factors, such as their surrounding environments, users' changing needs, and constrained resources. To handle these factors, most of the intelligent service robots are controlled by a task‐based control system, which generates a task plan that represents a sequence of actions, and executes those actions by invoking the corresponding functions. However, the traditional task‐based control systems lack the consideration of resource factors even though intelligent service robots have limited resources (limited computational power, memory space, and network bandwidth). Moreover, system‐specific concerns such as the relationships among functional modules are not considered during the task generation phase. Without considering both the resource conditions and interdependencies among software modules as a whole, it will be difficult to efficiently manage the functionalities that are essential to provide core services to users. In this paper, we propose a mechanism for intelligent service robots to efficiently use their resources on‐demand by separating system‐specific information from task generation. We have defined a sub‐architecture that corresponds to each action of a task plan, and provides a way of using the limited resources by minimizing redundant software components and maintaining essential components for the current action. To support the optimization of resource consumption, we have developed a two‐phase optimization process, which is composed of the topological and temporal optimization steps. We have conducted an experiment with these mechanisms for an infotainment robot, and simulated the optimization process. Results show that our approach contributed to increase the utilization rate by 20% of the robot resources. Copyright © 2011 John Wiley & Sons, Ltd.     

udpSkeduler: A Web architecture based decision support system for course and classroom scheduling

A key process for post-secondary educational institutions is the definition of course timetables and classroom assignments. Manual scheduling methods require enormous amounts of time and resources to deliver results of questionable quality, and multiple course and classroom conflicts usually occur. This article presents a scheduling system implemented in a Web environment. This system generates optimal schedules via an integer-programming model. Among its functionalities, this system enables direct interaction with instructors in order to gather data on their time availability for teaching courses. The results demonstrate that significant improvements over the typical fully manual process were obtained.     

Visual understanding industrial workflows under uncertainty on distributed service oriented architectures

Service Oriented Architecture (SOA) is an evolution of distributed computing based on the request/reply design paradigm for synchronous and asynchronous applications. In such architectures, application developers or system integrators can build scenarios by composing one or more services without knowing the services’ underlying implementations. In this paper, we adopt a SOA framework for on-line scheduling complex industrial workflows. The proposed SOA consists of three main layers; the input layer, the benchmarking layer, the prediction layer and the scheduler. The main innovation of our SOA architecture is the prediction layer that supports computer vision tools able to visually observe how an industrial workflow is actually executed. This way, we can automatically estimate the actual execution time for a process. In particular a new self-initialized visual tracker algorithm is proposed in this paper to robustly trace workers’ trajectory in a plant via visual observations. Then, part-to-whole curve matching is presented so as to find correspondences among the traced curve and the ideal one and thus improving scheduler efficiency. The input layer interoperably describes industrial operations using the XPDL (an XML-based) format. The benchmarker evaluates much faster than real-time and in an off-line mode how long it takes for an industrial workflow to be executed on a given resource guaranteeing an almost real-time implementation of the video processing algorithms on the plant. The last component of the proposed SOA is the scheduler with the goal to assign the workflows to the available resources. In this paper, a Maximum Benefit First (MBF) scheduler is presented which maximizes the total gain received by the industry when completing execution of all the beneficial operations with minimum violations of their delivery deadlines (that is with the minimum compensations). Experiments have been conducted on a real-world industrial plant of Nissan Iberica automobile construction indicating the efficiency of the proposed system.     

智能粮库曲面建模的设计与实现

在智能粮库计量系统中,粮面三维图形的还原与粮食质量的计算是粮库监管的一项重要内容．本系统采取将超声波传感器等设备非均匀地布置于粮仓内,用以获取粮面的部分信息,在合适的数学模型下还原出粮面的三维图形,并计算出粮食的体积和粮库的储粮质量,不仅能大幅度降低系统成本,而且具有安全、可靠、直观、高效等优点．     

基于知识的高速主轴系统智能设计

为提高制造企业设计效率和设计水平,以高速主轴系统设计开发为研究对象,提出了一种基于知识的高速主轴系统设计框架。采用本体论的知识建模方法,实现知识的重用,并重点阐述了规则知识描述、实例知识描述、知识处理模板等关键技术在高速主轴系统平台设计中的应用。该系统集成了主轴设计的经验、知识和过程,实现了知识共享,能帮助设计人员快速有效地完成高速主轴系统的智能设计。     

物联网在智能家居领域的应用

介绍了物联网的基本概念、核心技术以及在物联网背景下智能家居行业的发展与应用。智能家居利用物联网的网络通信技术、自动控制技术、音视频技术等对住宅内的家用电器、灯光照明进行智能控制,并结合其他系统为用户提供一个温馨舒适、安全节能的家居环境,让用户在生活中充分享受更多的方便与精彩。     

Building of road boundary map based on laser radar

A method for road boundary detection and tracking using laser ladar with respect to a vehicle’s local coordinates is proposed.It can be applied to different types of road conditions,such as roads with or without curbs,having relatively rough road surface and with obstacles on road surface.In the method,some line segments are extracted after a series of preprocessing on range data.The extracted line segments are combined and further selected.They are then united to match the road models and generate the road boundary points which are tracked by Kalman filter.Then the obtained road boundary points are transformed to build a precise vector map by least squares fitting algorithm.These fitted line segments represent road boundary vectors.The vector map is precise enough to provide ample road information such as the orientation of road,the road width and the passable road region.Finally,extensive experiments conducted in urban and semi-urban environment demonstrate the robustness,effectiveness and viability of the proposed method.