Tardiness heuristic for scheduling Flexible Manufacturing Systems

Abstract

This paper evaluates the tardiness performance of a sampling-based adaptive heuristic in a dynamic manufacturing environment. A test bed, following a real world manufacturing system, has been developed. The proposed algorithm has been implemented in this simulated environment. After fine tuning the algorithm, it has been tested in various shop conditions. The results of these simulation studies are summarized.     

A heuristic model for the sequence-dependent lot scheduling problem

This paper presents a heuristic algorithm for finding a good solution for the sequence-dependent lot scheduling problem. Unlike available methods, the algorithm eliminates the need for creating new artificial problems and implementing feasibility tests. It also eliminates the tedious task of translating setup relationships into a mathematical programming formulation. The result is a conceptually simple solution technique that is practically motivated and easily implemented for use on the shop floor. Comparison of algorithm performance with published results demonstrates the efficacy of the approach.     

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.     

A heuristic algorithm for the period vehicle routing problem

In this paper we consider the period vehicle routing problem, which is the problem of designing routes for delivery vehicles to meet customer service level requirements (not all customers require delivery on every day in the period). A heuristic algorithm, based upon the daily vehicle routing algorithm of Fisher and Jaikumar, is presented and computational results are given for test problems drawn from the literature.     

Quantitative models for optimal rest period scheduling

Mathematical and simulation models studying work-rest schedules in a production process are developed to arrive at an optimal rest policy to maximize work output per unit time. A CSMP simulation study is used to test the sensitivity of the results for different specific cases.     

An efficient heuristic procedure for solving the layout design problem

The limited ability of schematic procedures, constraints of linear programming techniques, inflexibility of construction methods and inadequacy of dynamic programming approaches to provide acceptable solutions to realistic size layout design problems has led to an ever increasing interest in heuristic procedures. Comparative studies have shown that heuristic procedures can satisfy more desirable qualities in an ‘ideal algorithm’ to a greater extent than competitive techniques. Excessive computational effort, which has been one of the main criticisms levelled against heuristic approaches in the past, proves to be less of a problem in relation to layout design. By utilizing unique attributes associated with real-life problems and using small incisive modifications it is demonstrated how a heuristic procedure can be significantly improved.     

A heuristic approach for component scheduling on a high-speed PCB assembly machine

The collect-and-place machine is one of the most widely used placement machines for assembling electronic components on the printed circuit boards (PCBs). Nevertheless, the number of researches concerning the optimisation of the machine performance is very few. This motivates us to study the component scheduling problem for this type of machine with the objective of minimising the total assembly time. The component scheduling problem is an integration of the component sequencing problem, that is, the sequencing of component placements; and the feeder arrangement problem, that is, the assignment of component types to feeders. To solve the component scheduling problem efficiently, a hybrid genetic algorithm is developed in this paper. A numerical example is used to compare the performance of the algorithm with different component grouping approaches and different population sizes.     

An exchange heuristic for resource constrained scheduling with consideration given to opportunities for parallel processing

This paper describes a heuristic which produces efficient makespans for resource-constrained scheduling problems with parallel processing capabilities. This heuristic was initially developed for the scheduling of army battalion training exercises. The original heuristic has also been successfully applied to solve problems in project scheduling with limited resources, generalized job shop scheduling, and resource-constrained scheduling. The exchange heuristic requires an initial feasible solution upon which it improves the makespan by efficiently and systematically shuffling activities while maintaining feasibility. The method has recently been modified twice, termed the intelligent version and naive version, respectively, such that its ability to reduce the initial makespan is enhanced. In this study     

A hybrid heuristic for the uncapacitated single allocation hub location problem

The uncapacitated single allocation hub location problem (USAHLP), with the hub-and-spoke network structure, is a decision problem in regard to the number of hubs and location–allocation. In a pure hub-and-spoke network, all hubs, which act as switching points for internodal flows, are interconnected and none of the non-hubs (i.e., spokes) are directly connected. The key factors for designing a successful hub-and-spoke network are to determine the optimal number of hubs, to properly locate hubs, and to allocate the non-hubs to the hubs. In this paper two approaches to determine the upper bound for the number of hubs along with a hybrid heuristic based on the simulated annealing method, tabu list, and improvement procedures are proposed to resolve the USAHLP. Computational experiences indicate that by applying the derived upper bound for the number of hubs the proposed heuristic is capable of obtaining optimal solutions for all small-scaled problems very efficiently. Computational results also demonstrate that the proposed hybrid heuristic outperforms a genetic algorithm and a simulated annealing method in solving USAHLP.     

A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization

This article deals with the development of a heuristic for scheduling in a flowshop with the objective of minimizing the makespan and maximum tardiness of a job. The heuristic makes use of the simulated annealing technique. The proposed heuristic is relatively evaluated against the existing heuristic for scheduling to minimize the weighted sum of the makespan and maximum tardiness of a job. The results of the computational evaluation reveal that the proposed heuristic performs better than the existing one.     

Time aggregation in production control and scheduling: towards efficient decision-support systems

A software system is developed for efficient optimal scheduling and production control in process industries modelled by production departments separated by buffers in serial or recycled paths. The new concept of time aggregation presented is easily implementable allowing a very fast solution of the optimal control of buffer levels. This optimal control problem is a large scale singular one (due to the chosen cost function) conveniently solved by a special technique of hierarchical calculus:'the iterative solution of a sequence of nonsin-gular problems converging to the singular one. Numerical results applied to a pulp and paper mill show that the new algorithm is substantially faster than the one previously used. This fact allowed the development of a complete software platform, presented in the paper, composed of several modules: modelling of industrial complex, (re)configuration, simulation, optimization, user interface—aiming at the realization of a decision support system for interactive use by daily operators and in instruction activities.     

Verifying safety critical task scheduling systems in PPTL axiom system

This paper presents a case study of formal verification of safety critical task scheduling systems. First, a scheduling algorithm described in a temporal logic programming language is presented; then a sufficient and necessary condition for the schedulability of task set is formalized. Further, the correctness of the condition is proved by means of theorem proving in the axiom system of Propositional Projection Temporal Logic.     

An efficient scheduling algorithm for the hot coil making in the steel mini-mill

This paper investigates and suggests an efficient solution to the problem of scheduling the steel making line in the Mini Steel Mill, which consists of three major processes: molten steel making, continuous slab casting, and hot charged rolling. Careful synchronization of these processes is a key productivity factor, since a very limited amount of work-in-process inventory is allowed. Since each process must run in batch, the schedule for the Mini-Mill consists of grouping and sequencing of lots for each process. However, each process has its own criteria for judging the quality of its lot grouping, which often conflicts with other processes. An efficient scheduling algorithm for the Mini-Mill is proposed. Numerical experiments with real world data suggest that the proposed algorithm yield satisfactory schedules very efficiently. The algorithm is currently used for the actual scheduling of a Mini-Mill in Korea.     

具有最大总加权满意度的单机调度问题的dynasearch算法

研究了总加权满意程度最大化的单机调度问题.对最优解的性质进行分析和证明,提出该类问题的统治规则.提出该问题新的基于dynasearch 邻域的迭代局域搜索算法(ILS).算法主要特点:1)dynasearch 是基于多摄动的思想,即一次可以做多个相互独立的交换(或插入);2)用动态规划获得最优dynasearch移动;3)ILS采用随机kick 策略对局部最优解进行摄动,然后继续迭代.实现了该问题的两种dynaearch算法;把两种dynasearch算法与统治规则相结合;在进行kick时引入误差限制.实验表明:嵌入统治规则的算法优于没有统治规则的算法;基于dynasearch交换的ILS 优于基于dynasearch插入的ILS;dynaearch算法要优于以交换为邻域的多初始点改进算法.     

Online LPT algorithms for parallel machines scheduling with a single server

We consider two parallel machines scheduling problems with a single server. For the general case we present an online LPT algorithm with competitive ratio 2, and give a lower bound $\frac{\sqrt{5} + 1}{2}$ . We also apply the online LPT algorithm to the special case where all the setup times are equal to 1. We show that the competitive ratio is 1.5, and no online algorithm can has a competitive ratio less than  $\sqrt{2}$ .