A parallel algorithm for two-staged two-dimensional fixed-orientation cutting problems

In this paper, we study the two-staged two-dimensional fixed-orientation cutting problem. We investigate the use of the parallel beam search algorithm for approximately solving the problem. The beam-search can be viewed as a truncated tree-search in which a subset of generated nodes are investigated. The proposed approach tries to explore some of these nodes in parallel by applying a master-slave paradigm. The master processor serves to guide the search-resolution by using a best-first search strategy for selecting the successive sets of nodes, called elite nodes. Whereas each slave processor develops the search tree and updates the global list of the master processor in an asynchronous manner. Each processor is based on combining a partial lower bound and a complementary upper bound, obtained by solving a series of bounded knapsack problems. The proposed method is analyzed computationally on a set of benchmark instances of the literature and their results are compared to those provided by existing algorithms. Encouraging and new results have been obtained.     

Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors

In the classical scheduling theory, it is widely assumed that a task can be processed by only one processor at a time. With the rapid development of technology, this assumption is no longer valid. In this work we present a problem of scheduling tasks, each of which requires for its processing a set of processors simultaneously and which can be executed on several alternative sets of processors. Scheduling algorithms based on dynamic and linear programming are presented that construct minimum length non-preemptive and preemptive schedules, respectively. Results of computational experiments are also reported.This research was partially supported by a KBN grant and by project CRIT.     

多机排序问题pm｜fix_j，pmtn｜C_（max）的多项式时间算法

在经典排序论中，一般都作以下两条假设：其一是每台机器在任一时刻至多加工一个零件，其二是每个零件在任一时刻至多被一台机器加工．在这篇文章中，研究多台机器可同时加工一个零件的多机排序问题，且每个零件可在固定的一个机器的子集上加工．本文在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究了这种问题的计算复杂性．     

Improved particle swarm algorithm for hydrological parameter optimization

In this paper, a new method named MSSE-PSO (master-slave swarms shuffling evolution algorithm based on particle swarm optimization) is proposed. Firstly, a population of points is sampled randomly from the feasible space, and then partitioned into several sub-swarms (one master swarm and other slave swarms). Each slave swarm independently executes PSO or its variants, including the update of particles’ position and velocity. For the master swarm, the particles enhance themselves based on the social knowledge of master swarm and that of slave swarms. At periodic stage in the evolution, the master swarm and the whole slave swarms are forced to mix, and points are then reassigned to several sub-swarms to ensure the share of information. The process is repeated until a user-defined stopping criterion is reached. The tests of numerical simulation and the case study on hydrological model show that MSSE-PSO remarkably improves the accuracy of calibration, reduces the time of computation and enhances the performance of stability. Therefore, it is an effective and efficient global optimization method.     

Scheduling problems in master-slave model

We consider scheduling problems in the master slave model, which was introduced by Sahni in 1996. The goal is to minimize the makespan and the total completion time. It has been shown that the problem of minimizing makespan is NP-hard. Sahni and Vairaktarakis developed some approximation algorithms to generate schedules whose makespan is at most constant times the optimal. In this paper, we show that the problem of minimizing total completion time is NP-hard in the strong sense. Then we develop algorithms to generate schedules whose total completion time and makespan are both bounded by some constants times their optimal values. Research supported in part by the National Science Foundation through grant DMI-0300156.     

Scheduling multiprocessor tasks with chain constraints

This paper is concerned with a new model in deterministic scheduling theory, where certain tasks may require more than one processor at a time. This model is motivated by several applications of multimicroprocessor systems and it has received much attention in the last years. In the paper it is assumed that each task can be processed on any processor subset of a given task-dependent size. Tasks are nonpreemptable and there are precedence constraints among them. It is proved that the problem of minimizing schedule length is NP-hard for three processors even if all the tasks have unit processing times and precedence constraints form a set of chains. Thus, it is unlikely to be solvable in polynomial time. On the other hand, two low order polynomial-time algorithms are given for the m processor case if processor requirements of the tasks in each chain are either uniform or monotonically decreasing (increasing).     

Synchronization of nonlinear fractional order systems

This paper deals with the master-slave synchronization scheme for partially known nonlinear fractional order systems, where the unknown dynamics is considered as the master system and we propose the slave system structure which estimates the unknown state variables. For solving this problem we introduce a Fractional Algebraic Observability (FAO) property which is used as a main tool in the design of the master system. As numerical examples we consider a fractional order Rössler hyperchaotic system and a fractional order Lorenz chaotic system and by means of some simulations we show the effectiveness of the suggested approach.     

Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints

This paper presents parallelization strategies for a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies exclusively on the decompostion of the solution space exploration. Four different parallel strategies are proposed and implemented on an asynchronous parallel machine under PVM: the master-slave model, with two different schemes for improved load balancing, and the single-program-multiple-data model, with single-token and multiple-token message passing schemes. The comparative analysis of these strategies shows that the tabu search approach for this problem is very suitable to the parallelization of the neighborhood search, with efficiency results almost always close to one for problems over a certain size.     

基于自适应模糊控制方法的四翼混沌系统有限时间同步

研究了一类带有未知外部摄动的四翼混沌主从系统的有限时间同步控制问题.首先,基于自适应模糊控制方法,对四翼混沌系统的不确定项进行了处理.其次,基于Lyapunov有限时间稳定性准则,设计了一种有限时间同步控制器,使得主系统与从系统能在有限时间内实现状态同步.最后,通过数值仿真,检验了该方法的有效性和鲁棒性.     

Statistical process control for monitoring scheduling performance—addressing the problem of correlated data

In both manufacturing and service operations effective scheduling plays an important role in achieving delivery performance and in utilizing resources economically. Classical scheduling theory takes a narrow, static view of performance. In reality the assessment of scheduling performance is a particularly difficult task. Typically scheduling is an activity that takes place repeatedly over time in the context of an overall planning and control architecture. Scheduling may be viewed as an activity within a process. Statistical Process Control (SPC) provides an attractive option for monitoring performance. In this paper we investigate the potential of applying SPC control charts in this context. The feasibility of monitoring flow time in a single processor model using control charts is studied using simulation. The application of control charts to monitor time-related measures in operational systems raises fundamental statistical problems. The need for approaches that are robust with respect to data correlation and lack of normality is shown to be an essential requirement. Residual-based approaches and the Exponentially Weighted Moving Average (EWMA) chart are shown to be reasonably effective in avoiding false alarms and in detecting process shifts. The applicability of the single processor model to more complex operational systems is discussed. The implications of the work for the design of performance monitoring and continuous improvement systems for time-related measures in manufacturing and service operations are considered. A number of areas are highlighted for further theoretical and practical studies.     

Single-machine scheduling with deteriorating functions for job processing times

In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier – this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions.     

A 2.79 COMPETITIVE ON-LINE ALGORITHM FOR TWO PROCESSOR REAL-TIME SYSTEMS WITH UNIFORM VALUE DENSITY

We consider the problem of competitive on-liae scheduling in two processor real-timesystems. In our model all tasks have common value density. Each task has a release time. an exe-cution time and a deadline. The scheduler is given no information about a task until it is released.And the value will be achieved if and only if the task is completed by its deadlirte. Moreover. wesuppose that migratbn is not allowed. The goal of the scheduler is to obtain as much value as pos-sible. In this paper we show that the competitive multipber of Safe-Risky-fixed Algorithm irt [4]is really 3 and presents a modified algorithm (Safe-Risky-unfixed Algorithm) that achieves a com-petitive mukiplier of 2. 79.     

Graph models for scheduling systems with machine saturation property

Let be a set of n independent tasks and a set of m processors. During each time instant, each processor can be used by a single task at most. A schedule is for each task an allocation of one or more time intervals to one or more processors. A schedule is said to be optimal if it minimizes the maximum completion time. We say a schedule S has the machine saturation property (MS property) if, at any time instant of task execution, all the machines are simultaneously busy. In this paper, we analyze the conditions under which a parallel scheduling system allows a schedule with the MS property. While for some simple models the analytical conditions can be easily stated, a graph model approach is required when conflicts of processor usage are present. For this reason, we define the class of saturated graphs that correspond to scheduling systems with the MS property. We present efficient graph recognition algorithms to verify the MS property directly on some classes of saturated graphs     

Hybrid control for synchronizing a chaotic system

In this paper, a hybrid control based on pulse width modulator (PWM) is proposed to synchronize a class of master–slave chaotic systems with uncertainties. We use the Genetic Algorithm (GA) together with fuzzy logic to tune the switching time of PWM mode controller such that the output response of master–slave chaotic system can be synchronized. Finally, an example, uncertain master–slave Duffing–Holmes chaos system, is proposed to show the proposed method’s effectiveness for chaotic synchronization.     

Synchronization of different-order chaotic systems: Adaptive active vs. optimal control

In this paper, an adaptive algorithm is proposed for synchronization of chaotic systems with different orders. A modular adaptive control strategy is applied to make states of the slave system track those of the master, despite the unknown parameters. One of the most advantages of the modularity approach, which is applied for the first time in chaos synchronization, is its flexibility in choosing identification and control modules and designing them completely independently. In this paper, a modified recursive least square algorithm is used to identify the unknown parameters of the slave system, and the control module is designed by means of two different algorithms. First it is designed based on active control method, and then, in order to synchronize with a lower energy, we design an optimal controller. The two methods are applied on a practical case study, and the results are compared. Two different dimensional neuron models, the HR neuron model and the cable model of cylindrical cell, are considered as the master and slave systems, respectively. Simulation results confirm the effectiveness of the proposed method.     

The customer response times in the processor sharing queue are associated

The customer response times in the egalitarian processor sharing queue are shown to be associated random variables under renewal inputs and general independent service times assumptions.The work by this author was supported in part by the National Science Foundation under grant ASC 88-8802764 and by the Office of Naval Research under grant ONR N00014-87-K-0796.     

Controlling job arrivals with processing time windows into Batch Processor Buffer

We consider a two-stage manufacturing system composed of a batch processor and its upstream processor. Jobs exit the upstream processor and join a queue in front of the batch processor, where they wait to be processed. The batch processor has a finite capacity Q, and its processing time is independent of the number of jobs loaded into the batch processor. In certain manufacturing systems (including semiconductor wafer fabrication), a processing time window exists from the time instance the job exits the upstream processor till the time instance it enters the batch processor. If a job is not processed before reaching the end of its processing time window, job rework or validation is required. We model this drawback by assigning a reward R for each successfully processed job by the upstream processor, and a penalty C for each job that reaches the end of its processing time window without being processed by the batch processor. We initially assume an infinite job source in front of the serial processor and also assume that the batch processor is operated under a threshold policy. We provide a method for controlling the production of the serial processor, considering the processing time window between the upstream processor and the downstream batch processor. We then show how the serial processor control policy can be modified when the serial processor also experiences intermittent job arrival.     

Logistics scheduling with batching and transportation

This paper studies a general two-stage scheduling problem, in which jobs of different importance are processed by one first-stage processor and then, in the second stage, the completed jobs need to be batch delivered to various pre-specified destinations in one of a number of available transportation modes. Our objective is to minimize the sum of weighted job delivery time and total transportation cost. Since this problem involves not only the traditional performance measurement, such as weighted completion time, but also transportation arrangement and cost, key factors in logistics management, we thus call this problem logistics scheduling with batching and transportation (LSBT) problem.     

Transient behavior of a two-processor heterogeneous system with catastrophes,server failures and repairs

In this paper, the transient behavior dealing with a two-processor heterogeneous system with catastrophes, server failures and repairs is investigated, where tasks arrive according to a Poisson process and execution times are exponentially distributed. Each task requires exactly one processor for its execution and the scheduling policy is FCFS. For this model, the exact time dependent solutions of system size probabilities are obtained using the generating function technique. An explicit expression is also found for the time dependent mean and variance of the system size distribution .Moreover, the current system may be regarded as an extension to some previous studies such as that Dharmaraja [4]. Finally, numerical illustrations are used to discuss the system behavior.     

Master–slave synchronization of continuously and intermittently coupled sampled-data chaotic oscillators

In this paper, we consider the problem of synchronizing a master–slave chaotic system in the sampled-data setting. We consider both the intermittent coupling and continuous coupling cases. We use an Euler approximation technique to discretize a continuous-time chaotic oscillator containing a continuous nonlinear function. Next, we formulate the problem of global asymptotic synchronization of the sampled-data master–slave chaotic system as equivalent to the states of a corresponding error system asymptotically converging to zero for arbitrary initial conditions. We begin by developing a pulse-based intermittent control strategy for chaos synchronization. Using the discrete-time Lyapunov stability theory and the linear matrix inequality (LMI) framework, we construct a state feedback periodic pulse control law which yields global asymptotic synchronization of the sampled-data master–slave chaotic system for arbitrary initial conditions. We obtain a continuously coupled sampled-data feedback control law as a special case of the pulse-based feedback control. Finally, we provide experimental validation of our results by implementing, on a set of microcontrollers endowed with RF communication capability, a sampled-data master–slave chaotic system based on Chua’s circuit.