Improved Task and Resource Partitioning Under the Resource-Oriented Partitioned Scheduling

Coordinated partitioning and resource sharing have attracted considerable research interest in the field of real-time multiprocessor systems. However, finding an optimal partition is widely known as NP-hard, even for independent tasks. A recently proposed resource-oriented partitioned (ROP) fixed-priority scheduling that partitions tasks and shared resources respectively has been shown to achieve a non-trivial speedup factor guarantee, which promotes the research of coordinated scheduling to a new level. Despite the theoretical elegance, the schedulability performance of ROP scheduling is restricted by the heuristic partitioning methods used in the original study. In this paper, we address the partitioning problem for tasks and shared resources under the ROP scheduling. A unified schedulability analysis framework for the ROP scheduling is proposed in the first place. A sophisticated partitioning approach based on integer linear programming (ILP) is then proposed based on the unified analysis. Empirical results show that the proposed methods improve the schedulability of ROP scheduling significantly, and the runtime complexity for searching a solution is reduced prominently compared with other ILP-based approaches as well.

     

On-line Scheduling for Jobs with Arbitrary Release Times

This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time on m parallel identical machines. A tight bound is given for List Scheduling(LS) algorithm and a better algorithm is given for m2.AMS Subject Classifications: 90B35 (90C27).This research is supported by Singapore-MIT Alliance.     

Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system

Consider a resource allocation problem on the following system. A system consists of m identical parallel machines and is alive only when all the machines are alive. To keep a machine alive, it requires resources (material, fuel, etc.). Resources with various sizes arrive one by one and the goal is to keep the system alive as long as possible. The problem has applications in many areas such as sequencing of maintenance actions for modular gas turbine aircraft engines[1]. Using scheduling term…     

Improved Blocking Time Analysis and Evaluation for the Multiprocessor Priority Ceiling Protocol

The Multiprocessor Priority Ceiling Protocol （MPCP） is a classic suspension-based real-time locking protocol for partitioned fixed-priority （P-FP） scheduling. However, existing blocking time analysis is pessimistic under the P-FP ＋ MPCP scheduling, which negatively impacts the schedulability for real-time tasks. In this paper, we model each task as an alternating sequence of normal and critical sections, and use both the best-case execution time （BCET） and the worst-case execution time （WCET） to describe the execution requirement for each section. Based on this model, a novel analysis is proposed to bound shared resource requests. This analysis uses BCET to derive the lower bound on the inter-arrival time for shared resource requests, and uses WCET to obtain the upper bound on the execution time of a task on critical sections during an arbitrary time interval of △t. Based on this analysis, improved blocking analysis and its associated worst-case response time （WCRT） analysis are proposed for P-FP ＋ MPCP scheduling. Schedulability experiments indicate that the proposed method outperforms the existing methods and improves the schedulability significantly.     

On the determinacy of concurrent games on event structures with infinite winning sets

We consider nondeterministic concurrent games played on event structures and study their determinacy problem—the existence of winning strategies. It is known that when the winning conditions of the games are characterised by a collection of finite winning sets/plays, a restriction (called race-freedom) on the boards where the games are played guarantees determinacy. However the games may no longer be determined when the winning sets are infinite. This paper provides a study of concurrent games and nondeterministic winning strategies by analysing conditions that ensure determinacy when infinitely many events are played, that is, when the winning sets are infinite. The main result is a determinacy theorem for a class of games with a bounded concurrency property and infinite winning sets shown to be finitely decidable.     

Study on berth planning problem in a container seaport: Using an integrated programming approach

This paper provides an integrated solution for two common processes in a container seaport: namely, the Berth Allocation Process (BAP) and the Crane Scheduling Process (QCSP). These are formulated through a Bi-Level Programming (BLP) approach, which is used to characterize the highly interrelated relationships between the two processes and simultaneously, identify an integrated solution for both. The upper-level problem (BAP) is termed ‘NP-hard’ as its computational complexity increases exponentially with the number of incoming ships for mooring, while the lower-level problem (QCSP) is a mixed-integer linear program. A revised genetic algorithm and a branch-and-bound method (B&B) are then applied for the solutions of upper and lower level problems, respectively.     

A cutting plane approach for integrated planning and scheduling

In this paper we propose a branch-and-cut algorithm for solving an integrated production planning and scheduling problem in a parallel machine environment. The planning problem consists of assigning each job to a week over the planning horizon, whereas in the scheduling problem those jobs assigned to a given week have to be scheduled in a parallel machine environment such that all jobs are finished within the week. We solve this problem in two ways: (1) as a monolithic mathematical program and (2) using a hierarchical decomposition approach in which only the planning decisions are modeled explicitly, and the existence of a feasible schedule for each week is verified by using cutting planes. The two approaches are compared with extensive computational testing.     

Single machine scheduling with interfering job sets

We consider two single machine bicriteria scheduling problems in which jobs belong to either of two different disjoint sets, each set having its own performance measure. The problem has been referred to as interfering job sets in the scheduling literature and also been called multi-agent scheduling where each agent's objective function is to be minimized. In the first problem (P1) we look at minimizing total completion time and number of tardy jobs for the two sets of jobs and present a forward SPT-EDD heuristic that attempts to generate the set of non-dominated solutions. The complexity of this specific problem is NP-hard; however some pseudo-polynomial algorithms have been suggested by earlier researchers and they have been used to compare the results from the proposed heuristic. In the second problem (P2) we look at minimizing total weighted completion time and maximum lateness. This is an established NP-hard problem for which we propose a forward WSPT-EDD heuristic that attempts to generate the set of supported points and compare our solution quality with MIP formulations. For both of these problems, we assume that all jobs are available at time zero and the jobs are not allowed to be preempted.     

Real-Time Schedulability Tests for Preemptive Multitasking

When developing multitasking real-time systems, schedulability tests are used to formally prove that a given task set will meet its deadlines. A wide range of such tests have appeared in the literature. This tutorial acts as a guide to the major tests available for preemptive multitasking applications.     

Simultaneous re-design and scheduling of multiple effect evaporator systems

Evaporation is a key operation in many industries and its optimization is required for the efficient management of water and energy within the process. During the operation, dissolved solids settle on the heat exchange surfaces with the consequent increase in the heat transfer resistance. Therefore, periodic shutdowns of the trains of evaporators are required for the cleaning of the units in order to restore acceptable performance. In this work the simultaneous re-design and scheduling of multiple effect evaporation systems is addressed. A mixed integer nonlinear programming model based on a discrete time representation is proposed and applied to a typical evaporation system in the sugar industry with several multiple effect parallel lines and time decaying performance.     

A decentralized model for flow shop production with flexible transportation system

The recent advances in technology sectors often clash with traditional organizational paradigms which can limit or make difficult an efficient implementation in the real world. In this paper we show how it is possible to exploit the advantages of innovative technologies in manufacturing when these are supported by new and efficient methods for production management. More in details, we face a flow shop scheduling problem in a shoe manufacturing system in which overtaking of jobs is allowed thanks to an innovative transportation system. Overtaking means that a job can be put in waiting state and another job can surpass it, allowing the change of the scheduling sequence. Preemption is not allowed. The objective function of the problem is the minimization of the maximum lateness. We propose a decentralized model, based on multi-agent system theory, to represent the production cells of the plant and to include the potentiality offered by overtaking of jobs at decisional level. The adoption of a decentralized approach increases the system flexibility since each machine is able to solve its local scheduling problem. Adding or removing machines to the plant will not imply a change in the scheduling algorithms. The outcomes of this work are reached firstly through a formulation of the problem with three flow shop scheduling models, secondly through a comparison of the models with respect to different performance indicators. The results highlight as the decentralized approach is able to reach comparable performances with the centralized one for a relevant number of instances. Moreover sensitivity analysis shows as in the decentralized model the computational time required to solve bigger instances increases less quickly than in the case of centralized ones. Finally, simulations of the decentralized approach clarify as the correlation of the local solution procedure is effected by the number of machines of the flow shop and the coordination mechanism is effected by the number of the jobs to be scheduled.     

利用动态规划思想攻击MH背包密码

子集和问题是对于给定的整数序列a1,a2,…,an和整数M,决定等式a1x1 a2x2 … anxn=M,i,xi∈{0,1},是否有解的问题。这个问题已经证明是NP完全的。它是MH背包密码的安全性基础。文中将利用动态规划思想解决子集和问题,从而给出MH背包密码的有效攻击算法。     

基于进化规划求解Steiner Tree 问题

提出基于进化规划求解Ｓｔｅｉｎｅｒ Ｔｒｅｅ问题的新方法。通过和原有启发式算法的结合提高了进化算法的效率,仿真证明了进化规划算法的有效性。     

Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization

An efficient method based on particle swarm optimization (PSO) is developed to solve the Multiprocessor Task Scheduling Problem (MPTSP). To efficiently execute parallelized programs on a multiprocessor environment, a scheduling problem must be solved to determine the assignment of tasks to the processors, the execution order of the tasks, and the starting time of each task, such that some optimality criteria are met. The scheduling problem is known as an NP-complete problem even when the target processors are fully connected and no communication delay is considered among the tasks in the task graph. The complexity of the scheduling problem depends on the number of tasks (N), the number of processors (M), the task processing time and the precedence constraints. The Directed Acyclic Graph (DAG) was exploited to represent the tasks and their precedence constraints. The proposed algorithm was compared with the Genetic Algorithm (GA) and the Duplication Scheduling Heuristic (DSH). We also provide a systematic investigation on the effect of varying problem settings. The results show that the proposed algorithm could not outperform the DSH while it could outperform the GA in some cases.     

A computational study of DEA with massive data sets

Data envelopment analysis (DEA) is computationally intensive. This work answers conclusively questions about computational performance and scale limits of the standard LP-based procedures currently used. Examples of DEA problems with up to 15K entities are documented and it is not hard to imagine problem size increasing as new more sophisticated applications are found for DEA. This work reports on a comprehensive computational study involving DEA problems with up to 100K DMUs. We explore the impact of different LP algorithms including interior point methods as well as accelerators such as advanced basis starts and DEA specific enhancements such as “restricted basis entry” (RBE). Our results demonstrate that solution times behave close to quadratically and that massive problems can be solved efficiently. We propose ideas for extending DEA into a data mining tool.     

Constructive Sets in Computable Sets

The original interpretation of the constructive set theory CZF in Martin-Loef‘s type theory uses the‘extensional identity types’.It is generally believed that these‘types’do not belong to type theory.In this paper it will be shown that the interpretation goes through without identity types.This paper will also show that the interpretation can be given in an intensional type theory.This reflects the computational nature of the interpretation.This computational aspect is reinforced by an ω-Set moel of CZF.     

Rough sets

We investigate in this paper approximate operations on sets, approximate equality of sets, and approximate inclusion of sets. The presented approach may be considered as an alternative to fuzzy sets theory and tolerance theory. Some applications are outlined.     

硬实时系统中基于软件容错模型的容错调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因此硬实时系统必须具有实时性和可靠性保障.软件容错模型是提高硬实时系统容错能力的一种有效方法.针对硬实时系统中容错优先级两种分配策略存在的不足,基于软件容错模型提出了一种容错优先级可提升的双重优先级分配策略.该方法通过为替代版本分配双重优先级,不仅能够提高硬实时系统的容错能力,同时还能够显著减少任务间的抢占次数.为了获得双重优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,首先提出了一种最大的双重优先级配置搜索算法(MDPCSA).然后结合MDPCSA算法,提出了一种最优的双重优先级配置搜索算法（ODPCSA）.仿真实验表明,与两种分配策略相比,在提高系统容错能力和降低抢占开销方面更为有效.