共查询到20条相似文献,搜索用时 36 毫秒
1.
In practice, machine schedules are usually subject to disruptions which have to be repaired by reactive scheduling decisions. The most popular predictive approach in project management and machine scheduling literature is to leave idle times (time buffers) in schedules in coping with disruptions, i.e. the resources will be under-utilized. Therefore, preparing initial schedules by considering possible disruption times along with rescheduling objectives is critical for the performance of rescheduling decisions. In this paper, we show that if the processing times are controllable then an anticipative approach can be used to form an initial schedule so that the limited capacity of the production resources are utilized more effectively. To illustrate the anticipative scheduling idea, we consider a non-identical parallel machining environment, where processing times can be controlled at a certain compression cost. When there is a disruption during the execution of the initial schedule, a match-up time strategy is utilized such that a repaired schedule has to catch-up initial schedule at some point in future. This requires changing machine–job assignments and processing times for the rest of the schedule which implies increased manufacturing costs. We show that making anticipative job sequencing decisions, based on failure and repair time distributions and flexibility of jobs, one can repair schedules by incurring less manufacturing cost. Our computational results show that the match-up time strategy is very sensitive to initial schedule and the proposed anticipative scheduling algorithm can be very helpful to reduce rescheduling costs. 相似文献
2.
A multi-agent architecture for dynamic scheduling of steel hot rolling 总被引:13,自引:0,他引:13
Peter I. Cowling Djamila Ouelhadj Sanja Petrovic 《Journal of Intelligent Manufacturing》2003,14(5):457-470
Steel production is a complex process and finding coherent and effective schedules for the wide variety of production steps, in a dynamic environment, is a challenging task. In this paper, we propose a multi-agent architecture for integrated dynamic scheduling of the hot strip mill (HSM) and the continuous caster. The scheduling systems of these processes have very different objectives and constraints, and operate in an environment where there is a substantial quantity of real-time information concerning production failures and customer requests. Each process is assigned to an agent which independently, seeks an optimal dynamic schedule at a local level taking into account local objectives, real-time information and information received from other agents. Each agent can react to real-time events in order to fix any problems that occur. We focus here, particularly, on the HSM agent which uses a tabu search heuristic to create good predictive–reactive schedules quickly. The other agents simulate the production of the coil orders and the real-time events, which occur during the scheduling process. When real-time events occur on the HSM, the HSM agent might decide whether to repair the current schedule or reschedule from scratch. To address this problem, a range of schedule repair and complete rescheduling strategies are investigated and their performance is assessed with respect to measures of utility, stability and robustness, using an experimental simulation framework. 相似文献
3.
4.
This paper reports our effort to develop a knowledge based system for scheduling jobs in a flexible manufacturing system (FMS). We view FMS scheduling as a two-stage process: static scheduling, followed by real-time rescheduling if unanticipated events were to occur. This paper deals with the static scheduling stage. The system uses a frame-based knowledge representation scheme and a problem-solving strategy based on filtered beam search. Filtered beam search views a scheduling problem as a state space search and generates a good schedule quickly by controlling the amount of search required. Evaluation functions are used to decide which branches are the most promising. An important feature of this system, in our view, is the explicit manner in which environmental, procedural and structural knowledge, (stored in the knowledge base using a frame-based scheme) can be used to improve the quality of the generated schedule. The system has been implemented and tested using Common Lisp on a Macintosh system with a 3MB main memory and a 40MB hard disk. Computational experience with our system is reported. 相似文献
5.
受损路网抢修是重特大自然灾害发生后开展应急处置和救援的一个基本前提,主要研究如何对道路抢修队进行合理的调度以快速恢复路网畅通、保障救援队伍和应急物资从出救点及时输送到各需求点.鉴于已有研究在面向大量需求点时往往很难给出有效的调度策略,首先基于路网模型和马尔科夫决策过程分析抢修队修复受损路网的关键因素,并设计一种双反馈回报函数;然后基于深度Q学习求解抢修队的最优调度策略;最后通过对比实验结果表明,在大量需求点环境下,所提出方法具有较好的稳定性和可靠性,兼顾受损路网的修复效率和运输效率,能够以更少的修复代价令所有需求点可达,为灾后复杂应急场景下的受损路网抢修提供有益的尝试. 相似文献
6.
This paper presents the use of Hopfield-type neural networks for process scheduling in the area of factory automation, where bus-based communication systems, called FieldBuses, are widely used to connect sensors and actuators to the control systems. We show how it overcomes the problem of the computational complexity of the algorithmic solution. The neural model proposed allows several processes to be scheduled simultaneously; the time required is polynomial with respect to the number of processes being scheduled. This feature allows real-time process scheduling and makes it possible for the scheduling table to adapt to changes in process control features. The paper presents the neural model for process scheduling and assesses its computational complexity, pointing out the drastic reduction in the time needed to generate a schedule as compared with the algorithmic scheduling solution. Finally, the authors propose an on-line scheduling strategy based on the neural model which can achieve real-time adaptation of the scheduling table to changes in the manufacturing environment. 相似文献
7.
8.
Simpson D.J. Burton F.W. 《IEEE transactions on pattern analysis and machine intelligence》1999,25(6):870-882
We model a deterministic parallel program by a directed acyclic graph of tasks, where a task can execute as soon as all tasks preceding it have been executed. Each task can allocate or release an arbitrary amount of memory (i.e., heap memory allocation can be modeled). We call a parallel schedule “space efficient” if the amount of memory required is at most equal to the number of processors times the amount of memory required for some depth-first execution of the program by a single processor. We describe a simple, locally depth-first scheduling algorithm and show that it is always space efficient. Since the scheduling algorithm is greedy, it will be within a factor of two of being optimal with respect to time. For the special case of a program having a series-parallel structure, we show how to efficiently compute the worst case memory requirements over all possible depth-first executions of a program. Finally, we show how scheduling can be decentralized, making the approach scalable to a large number of processors when there is sufficient parallelism 相似文献
9.
Deming Lei 《Computers & Industrial Engineering》2010,58(4):610-617
This paper presents the fuzzy job shop scheduling problem with availability constraints. The objective is to find a schedule that maximizes the minimum agreement index subject to periodic maintenance, non-resumable jobs and fuzzy due-date. A random key genetic algorithm (RKGA) is proposed for the problem, in which a novel random key representation, a new decoding strategy incorporating maintenance operation and discrete crossover (DX) are used. RKGA is applied to some fuzzy scheduling problem with availability constraints and compared with other algorithms. Computational results show that RKGA performs better than other algorithms. 相似文献
10.
It is well known that for preemptive scheduling on uniform
machines there exist polynomial time exact algorithms,
whereas for non-preemptive scheduling there are probably no such algorithms.
However, it is not clear how many preemptions (in total, or
per job) suffice in order to guarantee an optimal polynomial
time algorithm. In this paper we investigate
exactly this hardness gap,
formalized as two variants of the classic preemptive scheduling problem.
In generalized multiprocessor scheduling (GMS)
we have a job-wise or total bound on the number of preemptions
throughout a feasible schedule.
We need to find a schedule that satisfies the preemption
constraints, such that the maximum job completion time is
minimized.
In minimum preemptions scheduling (MPS)
the only feasible schedules are preemptive schedules with
the smallest possible makespan.
The goal is to find a feasible schedule that minimizes
the overall number of preemptions.
Both problems are NP-hard, even for two machines and zero preemptions.
For GMS, we develop polynomial time approximation schemes,
distinguishing between the cases where the number of machines
is fixed, or given as part of the input.
Our scheme for a fixed number of machines has linear
running time, and can be applied
also for instances where jobs have release dates,
and for instances with arbitrary preemption costs.
For MPS, we derive matching lower and upper bounds
on the number of preemptions required by any optimal schedule.
Our results for MPS hold for any instance in which a
job, Jj, can be processed simultaneously by ρj machines, for some ρj ≥ 1. 相似文献
11.
Manufacturing in a world class environment demands a high level of customer service. The production control department is responsible for achieving this high level of service through accurate planning and scheduling. The ability to achieve such a high level of customer service is limited by the scheduling tools currently available. Production planning is typically performed using MRP infinite capacity, fixed lead-time, backward scheduling. The work in each MRP time-bucket is then sequenced to develop a schedule. The production floor however, is not a static environment. Dynamic events, that cannot be scheduled, degrade production performance relative to the projected schedule. In this paper the relationship between dynamic events and schedule degradation is examined. Common approaches to production scheduling underestimate the effect of capacity loading relative to unplanned events and schedule achievability. These dynamic events exhaust capacity previously allocated to production orders. To hedge against such known, but unscheduled events, production control can schedule resources to a level less than full capacity. The size of the capacity hedge and the duration of the unplanned event dictate the time to recover from the backlog created by these dynamic events. A performance metric is developed to measure the ability to achieve customer promise dates. A machine loading policy is also presented to achieve the optimal capacity hedge point that will maximize this performance measure. The results are compared to simulated failures to examine the accuracy of the predicted performance degradation. The results suggest a trade-off of throughput for improved performance to customer promise date. 相似文献
12.
Generalized switched server system, a discretely controlled continuous‐time system, in which N tanks are used to represent N parallel entities, respectively, can be employed to address a class of load‐balancing problems. A tank‐pair model is a system that consists of two tanks and a single input single output controller, which regulates the inflows of the two tanks to acquire the two uniform levels under the specified inflow constraints. According to a quantized observation of the N tank levels, some discrete events are generated, and based on certain event feedback strategy, switching the location of the tank‐pair can control all the N tanks in a time‐sharing manner to acquire the N levels uniformity. Different from some existing scheduling strategies, this study proposes a fuzzy scheduling strategy (FSS) for such generalized switched server systems. Special measures are taken to reduce the N‐inputs two‐outputs fuzzy inference to a two‐inputs one‐output one, which greatly facilitates fuzzy scheduler design. Simulation results show that the proposed FSS strategy outperforms over the three existing scheduling strategies as a whole, and they also show that the proposed FSS strategy demonstrates high robustness over system heterogeneity. © 2009 Wiley Periodicals, Inc. 相似文献
13.
《Advanced Robotics》2013,27(1-2):103-122
In this paper, we address a multiple robot rearrangement problem. For different applications, problem-solving methods should be able to cope with various working environments. We focus on small working environments in particular with a concentrated arrangement of objects and narrow corridors. In this type of environment, the rearrangement problem can be very complicated because of high computational cost for priority settings to prevent robots from colliding and constraints related to the order of transportation. We propose a practical algorithm that divides a complicated rearrangement problem into simple subproblems. In our method, the rearrangement problem can be reduced to a project scheduling problem using a territorial approach. The application of a territorial approach can relax the complexity of priority settings, but yields new kinds of constraints at the same time. We propose an extended project scheduling problem solver to address these constraints. The solver is constructed on the basis of meta-heuristic strategy and generates the order of transportation that observes constraints. The proposed method is tested in a simulated environment with up to four mobile robots and 12 movable objects. Simulation results show the effectiveness of our method with respect to the applicability and a reasonable calculation time. 相似文献
14.
Harold F. O'Neil Jr. Yujing Ni Eva L. Baker Merlin C. Wittrock 《Computers in human behavior》2002,18(6)
The human benchmarking approach attempts to assess problem solving in expert systems by measuring their performance against a range of human problem-solving performances. We established a correspondence between functions of the expert system GATES and human problem-solving skills required to perform a scheduling task. We then developed process and outcome measures and gave them to people of different assumed problem-solving ability. The problem-solving ability or “intelligence” of this expert system is extremely high in the narrow domain of scheduling planes to airport gates as indicated by its superior performance compared to that of undergraduates, graduate students and expert human schedulers (i.e. air traffic controllers). In general, the study supports the feasibility of using human benchmarking methodology to evaluate the problem-solving ability of a specific expert system. 相似文献
15.
开放计算环境下的实时与非实时任务不确定并发,以及多种实时约束混合的复杂约束系统,即开放混合实时系统的需求越来越广泛.通过引入接收控制、调度服务器、自适应调节机制,提出一种开放环境下的自适应实时系统调度架构--OARtS(open adaptive real-time scheduling).它能适应开放计算环境的不确定性,有控制地接受实时任务运行;可根据系统空闲计算带宽变化,自适应地调节任务的实时等级,使得系统运行在最优的实时性能上;对于软实时任务,可根据其计算带宽需求变化,自适应地调节其计算带宽分配,以适应任务执行时间时变引起的实时不确定性. 相似文献
16.
17.
《Journal of Parallel and Distributed Computing》1994,23(1):112-118
In multiprocessors with static allocation of processes to processors, scheduling can be done locally for each processor. The scheduling strategy may have dramatic effect on the execution time of a parallel program. It is NP-hard to find an optimal schedule, and very little is known on how close the heuristic solutions get. In order to obtain nontrivial performance bounds, this study focuses on a restricted class of parallel programs, viz., chain structured programs. The major result is a theorem stating that if certain program parameters are known the execution time of the optimal schedule can be calculated within a factor of 2, even though the optimal schedule is unknown. Using a previously developed tool, one can extract the necessary parameters from a parallel program. This technique makes it possible to compare the execution time for different scheduling strategies with the optimal case. The technique used for calculating the performance bounds gives important hints on how to design efficient scheduling algorithms for chain structured programs. 相似文献
18.
The paper focuses on evaluating constraint satisfaction search algorithms on application based random problem instances. The
application we use is a well-studied problem in the electric power industry: optimally scheduling preventive maintenance of
power generating units within a power plant. We show how these scheduling problems can be cast as constraint satisfaction
problems and used to define the structure of randomly generated non-binary CSPs. The random problem instances are then used
to evaluate several previously studied algorithms. The paper also demonstrates how constraint satisfaction can be used for
optimization tasks. To find an optimal maintenance schedule, a series of CSPs are solved with successively tighter cost-bound
constraints. We introduce and experiment with an “iterative learning” algorithm which records additional constraints uncovered
during search. The constraints recorded during the solution of one instance with a certain cost-bound are used again on subsequent
instances having tighter cost-bounds. Our results show that on a class of randomly generated maintenance scheduling problems,
iterative learning reduces the time required to find a good schedule.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
19.
I/O scheduling for digital continuous media 总被引:4,自引:0,他引:4
A growing set of applications require access to digital video and audio. In order to provide playback of such continuous
media (CM), scheduling strategies for CM data servers (CMS) are necessary. In some domains, particularly defense and industrial process control, the timing requirements of these applications
are strict and essential to their correct operation. In this paper we develop a scheduling strategy for multiple access to
a CMS such that the timing guarantees are maintained at all times. First, we develop a scheduling strategy for the steady state,
i.e., when there are no changes in playback rate or operation. We derive an optimal Batched SCAN (BSCAN) algorithm that requires minimum buffer space to schedule concurrent accesses. The scheduling strategy incorporates two key
constraints: (1) data fetches from the storage system are assumed to be in integral multiples of the block size, and (2) playback
guarantees are ensured for frame-oriented streams when each frame can span multiple blocks. We discuss modifications to the
scheduling strategy to handle compressed data like motion-JPEG and MPEG.
Second, we develop techniques to handle dynamic changes brought about by VCR-like operations executed by applications. We define a suite of primitive VCR-like operations that can be executed. We show that an unregulated change in the BSCAN schedule, in response to VCR-like operations, will affect playback guarantees. We develop two general techniques to ensure playback guarantees while responding
to VCR-like operations: passive and active accumulation. Using user response time as a metric we show that active accumulation algorithms
outperform passive accumulation algorithms. An optimal response-time algorithm in a class of active accumulation strategies
is derived. The results presented here are validated by extensive simulation studies. 相似文献
20.
Chao-Chin Wu Lien-Fu Lai Liang-Tsung Huang MingLung Chen 《The Journal of supercomputing》2012,62(1):399-430
Previously we have proposed a Layered Self-Scheduling (LSS) approach that is a hybrid MPI and OpenMP based loop self-scheduling approach for dealing with the heterogeneity problem on a cluster system consisting of multi-core compute nodes, where the allocation functions of several well-known schemes have been modified for better performance. Though LSS provides better performance than the conventional self-scheduling schemes, we found the performance can be improved further after our comprehensive experiments and analyses. The newly proposed task scheduling strategy, called Enhanced Layered Self-Scheduling (ELSS), aims at how to utilize the compute powers of multiple processor cores more efficiently in the master compute node and how to schedule tasks to have more stable performance improvements. We have evaluated the new task scheduling strategy by three benchmark applications: Matrix Multiplication, Monte Carlo Integration, and Mandelbrot Set Computation. It is recommended that the global scheduler adopts Guided Self-Scheduling (GSS) for all, and the local scheduler adopts the static scheme for applications with regular workload distribution but any scheme for applications with irregular workload distribution. Experimental results show the best speedups obtained by ELSS for the three benchmark programs are 1.373, 13.34 and 2.4, respectively, compared with that scheduled by LSS. 相似文献