Adaptive/predictive scheduling: review and a general framework

Abstract

Abstract. Effective production scheduling can have a dramatic impact on manufacturing productivity. In modern automated manufacturing systems, the ability to revise and adjust the schedule can help reduce indirect costs which comprise a large portion of manufacturing costs in those systems. The objective of the research discussed here has been to study the feasibility of automatically scheduling multi-machine complexes and adjusting the schedule on a real-time basis by a unified computer system. We arc investigating selective real-time schedule adaptation by distinguishing between schedule generation and regeneration tasks (which might not be cost-effective) from schedule adaptation/recovery tasks (basically, causing less cosily disruption of the original plans). The article describes our general framework for automatic adaptive/predictive scheduling that includes five main functions: scheduler; monitor;comparator; resolvcr; recovery adaptor. Some experimental results demonstrating the effectiveness of the framework are discussed.     

Scheduling a single semi-continuous batching machine

This paper addresses a new problem, called semi-continuous batch scheduling, which arises in the heating-operation of tube-billets in the steel industry. Each heating furnace can be regarded as a semi-continuous batching machine, which can handle up to C jobs simultaneously. The jobs in the same batch enter and leave the machine semi-continuously, which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time. In this paper the processing time of a batch depends on the capacity of the semi-continuous batching machine, the longest processing time of jobs in the batch and its size. The objectives are to schedule jobs on the machine so that the makespan and the total completion time are minimized. A schedule for a semi-continuous batching machine consists of a batching and sequencing for the batches. We propose the optimal properties of two different objective functions and present the different dynamic programming algorithms with a running time of O(n²), respectively.     

Constraint-based model for the cyclic multi-hoists scheduling problem

This article presents a method for the resolution of a material handling scheduling problem. The case studied is a real industrial problem. It consists of finding a cyclic schedule for hoist movements in a treatment surface shop. In this kind of facility, several hoists are used for all the handling operations and they have to share common zones. Then it is necessary to control that there is no collision. The mathematical formulation of the problem is based on a combination of disjunctive constraints. The constraints describe either movement schedule or collision avoidance. The resolution procedure presented identifies all the collision configurations and then uses a branch and bound-like algorithm to find the optimal solution of a given problem. The language chosen for our implementation is the constraint logic programming language: Prolog IV, which is able to solve constraints with rational variables. It actively uses the constraint propagation mechanism that can be found in several languages.     

Flow shop scheduling by transportation model

This paper describes the classical problem of scheduling n jobs on m machines in a flow shop. A schedule evaluation algorithm is presented, which for job-pairs, generates a schedule evaluation matrix. The matrix is the input data to a transportation problem, the solution of which gives near-optimal jobsequence and makespan. The performance of the algorithm is discussed.     

Dynamic scheduling of manufacturing job shops using extreme value theory

Most job shop scheduling approaches reported in the literature assume that the scheduling problem is static (i.e. job arrivals and the breakdowns of machines are neglected) and in addition, these scheduling approaches may not address multiple criteria scheduling or accommodate alternate resources to process a job operation. In this paper, a scheduling method based on extreme value theory (SEVAT) is developed and addresses all the shortcomings mentioned above. The SEVAT approach creates a statistical profile of schedules through random sampling, and predicts the quality or 'potential' of a feasible schedule. A dynamic scheduling problem was designed to reflect a real job shop scheduling environment closely. Two performance measures, viz. mean job tardiness and mean job cost, were used to demonstrate multiple criteria scheduling. Three factors were identified, and varied between two levels each, thereby spanning a varied job shop environment. The results of this extensive simulation study show that the SEVAT scheduling approach produces a better performance compared to several common dispatching rules.     

A Model for Master Production Scheduling in Uncertain Environments

In uncertain environments, the master production schedule (MPS) is usually developed using a rolling schedule. When utilizing a rolling schedule, the MPS is replanned periodically and a portion of the MPS is frozen in each planning cycle. The cost performance of a rolling schedule depends on three decisions: the choice of the replanning interval (R), which determines how often the MPS should be replanned; the choice of the frozen interval (F), which determines how many periods the MPS should be frozen in each planning cycle; and the choice of the forecast window (T), which is the time interval over which the MPS is determined using newly updated forecast data. This paper uses an analytical approach to study the master production scheduling process in uncertain environments without capacity constraints, where the MPS is developed using a rolling schedule. It focuses on the choices of F, R, and T for the MPS. A conceptual framework that includes all important MPS time intervals is described. The effects of F, R, and T on system costs, which include the forecast error, MPS change, setup, and inventory holding costs, are also explored. Finally, a mathematical model for the MPS is presented. This model approximates the average system cost as a function of F, R, T, and several environmental factors. It can be used to estimate the associated system costs for any combination of F, R, and T.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

A dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time

We study the problem of (off-line) broadcast scheduling in minimizing total flow time and propose a dynamic programming approach to compute an optimal broadcast schedule. Suppose the broadcast server has k pages and the last page request arrives at time n. The optimal schedule can be computed in O(k³(n+k)^k−1) time for the case that the server has a single broadcast channel. For m channels case, i.e., the server can broadcast m different pages at a time where m < k, the optimal schedule can be computed in O(n^k−m) time when k and m are constants. Note that this broadcast scheduling problem is NP-hard when k is a variable and will take O(n^k−m+1) time when k is fixed and m ≥ 1 with the straightforward implementation of the dynamic programming approach. The preliminary version of this paper appeared in Proceedings of the 11th Annual International Computing and Combinatorics Conference as “Off-line Algorithms for Minimizing the Total Flow Time in Broadcast Scheduling”.     

A heuristic approach to n/ m job shop scheduling: fuzzy dynamic scheduling algorithms

n/m shop scheduling is a ‘ NP-Hard’ problem. Using conventional heuristic algorithms ( priority rules) only, it is almost impossible to achieve an optimal solution. Research has been carried out to improve the heuristic algorithms to give a near-optimal solution. This paper advocates a fuzzy logic based, dynamic scheduling algoridim aimed at achieving this goal. The concept of new membership functions is discussed in die algorithm as a link to connect several priority rules. The constraints to determine the membership function of jobs for a particular priority rule are established, and three membership functions are developed. In order to decide the weight vector of priority rules, an aggregate performance measure is suggested. The methodology for constructing the weight vector is discussed in detail. Experiments have been carried out using a simulation technique to validate the proposed scheduling algorithm.     

PCB assembly scheduling through kit concept

This paper presents the design and test of a new scheduling environment dedicated to the off-line scheduling of PCB assembly shops. The main idea introduced is the employment of the 'kit concept' as a scheduling tool, as opposed to the traditional batch scheduling. In the kit approach, the basic PCB aggregations are kits composed of different PCBs matching finished products requirements, instead of homogeneous batches of identical boards. By introducing the kit approach, PCB assembly schedule is intended to be focused more towards the assembly of final products than towards the internal PCB assembly shop constraints and requirements. A simulation model and data from a real assembly system are used to compare the kit approach with traditional batch processing. Experimental results show that the proposed kit approach jointly achieves remarkable improvements in the effectiveness and efficiency performances of the assembly system, as compared to the batch approach. However, it is determined also that these advantages can only be achieved if a sufficiently advanced scheduling system is used.     

Simulation-based production schedule generation

Abstract

While simulation has been used in manufacturing for many years, predominantly for facility design, it is within the last few years, that simulation languages have been developed to a point where they can be used on a day-to-day basis to generate schedules and predict their performance. This paper describes our use of different modelling techniques to develop a production schedule generation system. An example describing a system for a small- to medium-sized order producing company using SIMAN/CINEMA is included. While addressing the shortcomings of existing scheduling systems it is shown how the approach taken is a feasible way of creating a dynamic goal-driven simulation-based production scheduler. The paper does not aim to describe an ‘off the shelf’ scheduling system product, but rather to give an overview to methods, techniques and experiences which enable us rapidly to tailor a simulation-based scheduling system to the specific needs of a company.     

On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time

Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times C _j is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time w _j C _j. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + )-competitive on-line algorithm for any > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.     

Flexible reasoning using sensible agent-based systems: A case study in job flow scheduling

Planning and control systems for highly dynamic and uncertain manufacturing environments require adaptive flexibility and decision-making capabilities. Modern distributed manufacturing systems assess the utility of planning and executing solutions for both system goals (e.g. minimize manufacturing production time for all parts or minimize WIP) and local goals (e.g. expedite part A production schedule or maximize machine X utilization). Sensible Agents have the ability to alter their autonomy levels to choose among a set of decision models in order to handle the differences between local and system goals. In this paper, Sensible Agents are applied to a production planning and control problem in the context of job shop scheduling and decision model theory. Sensible Agents provide for trade-off reasoning mechanisms among system and local utilities that are flexible and responsive to an agent's abilities, situational context and position in the organizational structure of the system.     

A simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

基于拍卖机制的资源转移时间型动态分布式多项目调度

实践中,企业并行实施地域上分散的多个项目时,资源在各子项目之间的转移时间是影响多项目整体进度的关键因素,同时在动态多项目环境下,新项目不断到达且到达时间不可预知使得制定多项目调度计划遭遇更大困难。本文在动态环境下对资源转移时间型分布式多项目调度问题进行建模和求解,基于多代理系统建立分布式多项目调度问题的动态模型,并将拍卖理论引入其中,设计一种基于时间窗拍卖机制的分布式多代理系统(DMAS/ATW),在动态环境和资源转移时间约束下为多项目配置全局资源。通过一个具体的分布式多项目示例详细分析DMAS/ATW算法的动态调度过程,并基于MPSPLIB中的分布式多项目算例开展数值实验。实验结果表明：无资源转移时间约束时,DMAS/ATW算法求得的平均项目延迟同比相关文献中的DMAS/RIA算法最多减少42%,平均减少26%;有资源转移时间约束时,DMAS/ATW算法对1/3算例集的求解结果优于DMAS/RIA算法在无资源转移时间约束时的结果,验证了本文DMAS/ATW算法求解效果的优异性。对算例规模和全局资源利用系数的实验分析还表明,DMAS/ATW算法对不同规模和资源约束紧张程度的算例都具有良好的适应性。     

A pairwise interchange algorithm for parallel machine scheduling

This paper considers the problem of non-preemptive scheduling n tasks on m identical parallel processors to minimize makespan for simultaneous arrivals. Based on a pairwise interchange method, an efficient algorithm ispresented which is able to give a near-optimal schedule in a short time through suitable pairwise interchange between tasks, after an initial solution is constructed. The behaviour of the algorithm is discussed. Testing results prove its high performance in comparison with available simple heuristic procedures. Finally, the algorithm is generalized for the problems of non-identical processors and non-simultaneous arrivals.     

Evaluation of safety stock methods in multilevel material requirements planning (MRP) systems

This paper evaluates alternative methods of establishing the safety stock level taking into consideration of historical measures of forecasting accuracy and the needs for master production scheduling and material requirement planning under a rolling time horizon. A computer model is used to simulate the forecasting, master production scheduling and material planning activities in a company that produces to stock and the production activities are managed by multilevel MRP systems. The simulation output is analysed to evaluate the impact of safety stock methods on MRP system performance. The result of the study shows that using safety stock can help to reduce total cost, schedule instability and improve service level in the MRP systems. Guidelines are developed to help managers select methods to determine safety stock in MRP system operations.     

Two-agent scheduling problems on a single-machine to minimize the total weighted late work

In this paper, two-agent scheduling problems are presented. The different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. The objective functions we consider are the total weighted late work and the maximum cost. The problem is to find a schedule that minimizes the objective function of agent A, while keeping the objective function of agent B cannot exceed a given bound U. Some different scenarios are presented by depending on the objective function of each agent. We address the complexity of those problems, and present the optimal polynomial time algorithms or pseudo-polynomial time algorithm to solve the scheduling problems, respectively.     

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

In this paper we consider a semi-online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi-online algorithm H that achieves a competitive ratio ρ _H (s) as a piecewise function in terms of the speed ratio s.