基于约束和邻域的炼钢连铸重调度算法

针对机器故障扰动,研究了炼钢连铸重调度问题及其求解算法。通过将机器故障映射为资源约束,建立了基于动态约束满足的炼钢连铸重调度模型,模型以最大化连浇量与调度方案相似度为目标。针对问题的模型及其特点,采用约束满足和邻域搜索相结合的混合算法对其进行了求解。仿真实验表明本文提出的模型和算法是有效的。     

A decomposition-based approach to flexible flow shop scheduling under machine breakdown

Manufacturing systems in real-world production are generally dynamic and often subject to a wide range of uncertainties. Recently, research on production scheduling under uncertainty has attracted substantial attention. Although some methods have been developed to address this problem, scheduling under uncertainty remains inherently difficult to solve by any single approach. This article considers makespan optimisation of a flexible flow shop (FFS) scheduling problem under machine breakdown. It proposes a novel decomposition-based approach to decompose an FFS scheduling problem into several cluster scheduling problems which can be solved more easily by different approaches. A neighbouring K-means clustering algorithm is developed to first group the machines of an FFS into an appropriate number of machine clusters, based on a proposed machine allocation algorithm and weighted cluster validity indices. Two optimal back propagation networks, corresponding to the scenarios of simultaneous and non-simultaneous job arrivals, are then selectively adopted to assign either the shortest processing time (SPT) or the genetic algorithm (GA) to each machine cluster to solve cluster scheduling problems. If two neighbouring machine clusters are allocated with the same approach, they are subsequently merged. After machine grouping and approach assignment, an overall schedule is generated by integrating the solutions to the sub-problems. Computation results reveal that the proposed approach is superior to SPT and GA alone for FFS scheduling under machine breakdown.     

Solving comprehensive dynamic job shop scheduling problem by using a GRASP-based approach

There are many dynamic events like new order arrivals, machine breakdowns, changes in due dates, order cancellations, arrival of urgent orders etc. that makes static scheduling approaches very difficult. A dynamic scheduling strategy should be adopted under such production circumstances. In the present study an event driven dynamic job shop scheduling mechanism under machine capacity constraints is proposed. The proposed method makes use of the greedy randomised adaptive search procedure (GRASP) by also taking into account orders due dates and sequence-dependent set-up times. Moreover, order acceptance/rejection decision and Order Review Release mechanism are integrated with scheduling decision in order to meet customer due date requirements while attempting to execute capacity adjustments. We employed a goal programming-based logic which is used to evaluate four objectives: mean tardiness, schedule unstability, makespan and mean flow time. Benchmark problems including number of orders, number of machines and different dynamic events are generated. In addition to event-driven rescheduling strategy, a periodic rescheduling strategy is also devised and both strategies are compared for different problems. Experimental studies are performed to evaluate effectiveness of the proposed method. Obtained results have proved that the proposed method is a feasible approach for rescheduling problems under dynamic environments.     

Rescheduling with controllable processing times for number of disrupted jobs and manufacturing cost objectives

We consider a machine rescheduling problem that arises when a disruption such as machine breakdown occurs to a given schedule. Machine unavailability due to a breakdown requires repairing the schedule as the original schedule becomes infeasible. When repairing a disrupted schedule a desirable goal is to complete each disrupted job on time, i.e. not later than the planned completion time in the original schedule. We consider the case where processing times of jobs are controllable and compressing the processing time of a job requires extra processing cost. Usually, there exists a nonlinear relation between the processing time and manufacturing cost. We solve a bicriteria rescheduling problem that trades off the number of on-time jobs and manufacturing cost objectives. We give a mixed-integer second-order cone programming formulation for the problem. We develop a heuristic search algorithm to generate efficient solutions for the problem. Heuristic algorithm searches solution space by moving and swapping jobs among machines. We develop cost change estimates for job moves and swaps so that the heuristic implements only promising moves and hence generates a set of efficient solutions in reasonably short CPU times.     

Analytical models to predict the performance of a single-machine system under periodic and event-driven rescheduling strategies

This article presents initial results in the search for analytical models that can predict the performance of one-machine systems under periodic and event-driven rescheduling strategies in an environment where different job types arrive dynamically for processing and set-up must incur when production changes from one product type to another. The scheduling algorithm considered uses a first-in firstout dispatching rule to sequence jobs and it also groups jobs with similar types to save set-up time. The analytical models can estimate important performance measures like average flow time and machine utilization, which can then be used to determine optimal rescheduling parameters. Simulation experiments are used to show that the analytical models accurately predict the performance of the single machine under the scheduling algorithm proposed.     

A robust optimization approach for integrated steel production and batch delivery scheduling with uncertain rolling times and deterioration effect

Efficient collaboration between various sub-processes of steel production is of considerable significance, which directly affects a product’s production cycle and energy consumption. However, current collaborative optimisation models and methods in steel production are still limited: (1) Most of the current collaborative manufacturing problems in steel production focus on obtaining joint schedule between steel-making and continuous casting (SCC), and the works considering continuous casting and hot rolling (CCHR) are very few. (2) The processing time is assumed as a constant in most of the existing SCC scheduling models. However, the rolling time of a product in hot rolling operation is actually uncertain and deteriorating. (3) Exact algorithms cannot be applied to solve the complicated collaborative optimisation problems because of their high complexities. To address these problems, we propose an integrated CCHR and batch delivery scheduling model where interval rolling time and linear deterioration effect are considered. With the concept of min–max regret value, we formulate the collaborative optimisation problem as a robust optimisation problem. Instead of using the exact algorithm, we develop an Improved Variable Neighborhood Search (IVNS) algorithm incorporated a novel population update mechanism and neighbourhood structures to solve the robust optimisation problem. Moreover, we develop an exact algorithm that combines CPLEX solver and two dynamic programming algorithms to obtain the maximum regret value of a given rolling sequence. The results of computational experiments show the excellent performance of the proposed algorithms.

Abbreviations: IVNS: improved variable neighbourhood search; TOPSIS: technique for order of preference by similarity to ideal solution; PUM-TOPSIS: population update mechanism based on TOPSIS; DP: dynamic programming; NSs-PUC: neighbourhood structures based on the parameterised uniform crossover; SNRT: shortest normal rolling time; SNRT-DP: DP algorithm based on SNRT rule; BRKGA: biased random-key genetic algorithm; SCC: steelmaking and continuous casting; MINP: mixed integer nonlinear programme; CCHR: continuous casting and hot rolling; PSO: particle swarm optimisation; GA: genetic algorithm; VNS-HS: variable neighbourhood search and harmony search; HPSO?+?GA: hybrid PSO and GA; SA: simulated annealing; B&B: branch-and-bound; TPSO: two-phase soft optimisation; TSAUN: tabued simulated annealing with united-scenario neighbourhood; VNS: variable neighbourhood search; ABC: artificial bee colony; PRVNS: population-based reduced variable neighbourhood search; NS1: neighbourhood structure 1; NS2: neighbourhood structure 2; DE: differential evolution; WSR: Wilcoxon signed-rank test; ENS: exchange neighbourhood structure; IVNS-ENS: IVNS with ENS; RPI: relative percentage increase; ARPI: average RPI; SD: standard deviation.     

Rescheduling parallel machines with stepwise increasing tardiness and machine assignment stability objectives

Nervousness in machine assignments during rescheduling can cause problems for the implementation of a scheduling system. This paper examines rescheduling due to the arrival of new jobs to the system. Parallel machine scheduling problems with stepwise increasing tardiness cost objectives, non-zero machine ready times, constraints that limit machine reassignments, and machine reassignment costs are considered. Simulation experiments and individual scheduling problems indicate that nervousness can be controlled at a low cost in some parallel machine scheduling environments. The rescheduling problems in the simulation are solved with a branch-and-price algorithm. Significant gains in schedule stability can be achieved by selecting the alternative optimal solution with the fewest machine reassignments.     

Auction-based approach to resolve the scheduling problem in the steel making process

Steel production is an extremely complex process and determining coherent schedules for the wide variety of production steps in a dynamic environment, where disturbances frequently occur, is a challenging task. In the steel production process, the blast furnace continuously produces liquid iron, which is transformed into liquid steel in the melt shop. The majority of the molten steel passes through a continuous caster to form large steel slabs, which are rolled into coils in the hot strip mill. The scheduling system of these processes has very different objectives and constraints, and operates in an environment where there is a substantial quantity of real-time information concerning production failures and customer requests. The steel making process, which includes steel making followed by continuous casting, is generally the main bottleneck in steel production. Therefore, comprehensive scheduling of this process is critical to improve the quality and productivity of the entire production system. This paper addresses the scheduling problem in the steel making process. The methodology of winner determination using the combinatorial auction process is employed to solve the aforementioned problem. In the combinatorial auction, allowing bidding on a combination of assets offers a way of enhancing the efficiency of allocating the assets. In this paper, the scheduling problem in steel making has been formulated as a linear integer program to determine the scheduling sequence for different charges. Bids are then obtained for sequencing the charges. Next, a heuristic approach is used to evaluate the bids. The computational results show that our algorithm can obtain optimal or near-optimal solutions for combinatorial problems in a reasonable computation time. The proposed algorithm has been verified by a case study.     

Self-adaptive dynamic scheduling of virtual production systems

To enhance the agility of virtual production systems (VPSs) under today's dynamic and changing manufacturing environment, a self-adaptive dynamic scheduling method based on event-driven is proposed for VPSs in this paper. This method is composed of the mechanisms and algorithm of self-adaptive dynamic scheduling. In the mechanisms, the dynamic events faced by VPSs are determined through users’ inputs or supervisory controllers’ detections, the local effects made on the schedule are analysed according to the dynamic events, and the self-adaptive measures and rules are specified correspondingly. To implement the dynamic scheduling of VPSs under the guidance of self-adaptive rules, a modified heuristic rescheduling algorithm is proposed for affected operations. A case study illustrates that the proposed method can well accomplish the dynamic scheduling of VPSs in a self-adaptive manner.     

Scheduling/rescheduling in the manufacturing operating system environment†

A scheduling/rescheduling procedure is proposed for real-time control of a computerized manufacturing facility managed by a central manufacturing operating system. The procedure implies schedule revisions upon significant operational changes such as machine breakdowns. Experiments to evaluate the total production time of a computerized manufacturing system with breakdowns under scheduling/rescheduling have yielded advantages of between 25% to 7-0% compared to fixed sequencing and priority despatching procedures, respectively. Computation times required for the scheduling procedures on a CDC 65OO/66OO have also been studied. The scheduling/rescheduling procedure for an actual facility required less than two minutes, and the computation time can be regulated by the selection of parameters in an approximate method of scheduling.

     

Using Functional Virtual Population as assistance to learn scheduling knowledge in dynamic manufacturing environments

When a scheduling environment is static and system attributes are deterministic, a manufacturing schedule can be obtained by applying analytical tools such as mathematical modelling technology, dynamic programming, the branch- and-bound method or other developed searching algorithms. Unfortunately, a scheduling environment is usually dynamic in a real manufacturing world. A production system may vary with time and require production managers to change schedule repeatedly. Therefore, the main aim here was to find a scheduling method that could reduce the need for rescheduling. An approach called Functional Virtual Population was proposed as assistance to learn robust scheduling knowledge for manufacturing systems under rationally changing environments. The used techniques include machine learning with artificial neural networks and IF-THEN scheduling rules. To illustrate the study in detail, a simulated flexible manufacturing system consisting of four machines, four parts, one automatic guided vehicle and eight buffers was built as the foundation for learning the concept. Also, Pythia software (a back-propagation-based neural networks) was employed as the learning tool in the learning procedure.     

Distributed supply‐chain project rescheduling: Part I—impacts of information‐sharing strategies

A supply‐chain project normally involves a number of independent and autonomous enterprises that share information to varying levels. The initial project schedule (preschedule) established at the time of forming the supply‐chain often requires a series of amendments due to unexpected or abrupt disturbances such as temporary resource outage (e.g. machine break), arrival or cancellation of orders from customers, and change in an operation's processing time (e.g. rework). Rescheduling or adaptive scheduling is a process of updating/repairing the preschedule to adapt to the disturbances. Appropriate rescheduling methods must be chosen and applied depending on the specific protocol of sharing information agreed between the enterprises in the supply chain. This paper is concerned with the impacts of different levels of information sharing on the performance of supply‐chain project rescheduling problems. Three rescheduling methods are examined in the research. They are distributed AOR (Affected Operations Rescheduling), negotiation‐based rescheduling (NEG), and centralized total rescheduling (TR). These three rescheduling algorithms represent three typical information‐sharing scenarios: little information sharing, limited information sharing and complete information sharing, respectively. A comprehensive computational study is conducted under different experimental settings. The results show that NEG and distAOR outperforms the TR rescheduling in terms of total cost minimization and stability of schedule and contractual relationship. NEG is superior in both rescheduling efficiency and effectiveness due to the effect of a moderate level of information sharing.     

Comparing the impact of different rescheduling strategies on the entropic-related complexity of manufacturing systems

The primary objective of this paper is to compare five rescheduling strategies according to their effectiveness in reducing entropic-related complexity arising from machine breakdowns in manufacturing systems. Entropic-related complexity is the expected amount of information required to describe the state of the system. Previous case studies carried out by the authors have guided computer simulations, which were carried out in Arena 5.0 in combination with MS Excel. Simulation performance is measured by: (1) entropic-related complexity measures, which quantify: (a) the complexity associated with the information content of schedules, and (b) the complexity associated with the variations between schedules; and (2) mean flow time. The results highlight two main points: (a) the importance of reducing unbalanced machine workloads by using the least utilised machine to process the jobs affected by machine breakdowns, and (b) low disruption strategies are effective at reducing entropic-related complexity; this means that applying rescheduling strategies in order to manage complexity can be beneficial up to a point, which, in low disruption strategies, is included in their threshold conditions. The contribution of this paper is two-fold. First, it extends the application of entropic-related complexity to every schedule generated through rescheduling, whereas previous work only applied it to the original schedule. Second, recommendations are proposed to schedulers for improving their rescheduling practice in the face of machine breakdowns. Those recommendations vary according to the manufacturing organisations’ product type and scheduling objectives. Further work includes: (a) preparing a detailed workbook to measure entropic-related complexity at shop-floor level; and (b) extending the analysis to other types of disturbances, such as customer changes.     

Predictable scheduling of a single machine with breakdowns and sensitive jobs

Production schedules released to the shop floor have two important functions: allocating shop resources to different jobs to optimize some measure of shop performance and serving as a basis for planning external activities such as material procurement, preventive maintenance and delivery of orders to customers. Schedule modification may delay or render infeasible the execution of external activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules that can absorb disruptions without affecting planned external activities while maintaining high shop performance. We present a predictable scheduling approach, that inserts additional idle time into the schedule to absorb the impacts of breakdowns. The effects of disruptions on planned support activities are measured by the deviations of job completion times in the realized schedule from those in the predictive schedule. We apply our approach to minimizing total tardiness on a single machine with stochastic machine failures. We then extend the procedure to consider the case where job processing times are affected by machine breakdowns, and provide specialized rescheduling heuristics. Extensive computational experiments show that this approach provides high predictability with minor sacrifices in shop performance.     

Dynamic response to demand variability for precast production rescheduling with multiple lines

Production scheduling plays a crucial role in the prefabricated construction productivity and on-time delivery of precast components (PCs). However, previous studies mainly focused on the static scheduling of single production line without considering the demand variability in practice. To achieve dynamic production planning, a Two-level Rescheduling Model for Precast Production with multiple production lines is developed to minimise the rescheduling costs based on genetic algorithm, from the two levels of (1) selection of production line and (2) rescheduling of jobs based on PCs’ priority. Further, two scenarios of different and shared mould types are investigated to represent real-world production environments. Finally, a real case study is conducted to test the validity of proposed rescheduling model. 58.1 and 48.5% cost savings are achieved by comparison to no response to changes and heuristic rescheduling methods, respectively. This research contributes to the precast production theory by expanding the insight into dynamic rescheduling with multiple production lines. The methodology will promote the on-time delivery of PCs and enhance the dynamic precast production management.     

A Dynamic Programming Model for Determining Continuous-Caster Configurations

In the steel industry the continuous casting machine, or caster, can be used to eliminate a number of processing steps associated with the traditional steel production sequence from ingot through blooms to finished product. A given continuous caster can produce only a small number of bloom thicknesses, which creates a problem for selecting those continuous-caster configurations which would maximize caster utilization. A dynamic programming model was developed to assist Bethlehem Steel personnel to determine that set of caster configurations which would maximize the cast bloom tonnage that could be processed through one of the finishing mills. Without the aid of such a model, selecting the highest productivity options presents a difficult exercise because of two conflicting considerations: (1) as the number of caster-produced bloom thicknesses increases, the caster setup time and configuration complexity increase; and (2) as the number of thicknesses decreases, less cast tonnage can be processed through the finishing mill because of reheat-furnace and cooling-bed limitations. The model results were transmitted to plant management and are being used in conjunction with other information to determine the most economic configuration.     

A batch splitting method for a job shop scheduling problem in an MRP environment

The job shop scheduling problem has been a major target for many researchers. Unfortunately though, most of the previous research was based on assumptions that are different from the real manufacturing environment. Among those distorted assumptions, two assumptions about set-up time and job composition can greatly influence the performance of a schedule. First, most of the past studies ignored the impact of the before-arrival set-up time. If we know the sequence of operations in advance, we can obtain an improved schedule by preparing the setup before a job arrives. Secondly, most of the past studies assumed that a job consists of only a single part, that is a batch of size one. However, if we assume that a job consists of a batch size greater than one, as in many real manufacturing environments, then we can obtain an improved schedule because we can fill up the idle times of machines with jobs which have smaller processing times by splitting the original batches. However, the number of job orders may then increase due to the split, and the size of the scheduling problem would become too large to be solved in a practical time limit. Consequently, there may be an optimum batch size considering trade-off between better solution and tractability. The current study is the result of an attempt to find an acceptable solution when the production requirement from a MRP system for a planning period exceeds the capacity of a production system. We try to get an improved schedule by splitting the original batch into smaller batches, and consider setting up a machine before the actual arrival of jobs to that machine. Thereby we can meet the due date requirement without resorting to rescheduling of the master production schedule. For the given batch, we disaggregate it according to the algorithm we are proposing. A so-called 'modified shifting bottleneck procedure' is then applied to solve the job shop scheduling problem with a before-arrival family set-up time considering release date, transportation time and due date. The study also shows that we can adapt to unexpected dynamic events more elegantly by allowing the splitting of batches.     

Scheduling continuous aluminium casting lines

This study considers the problem of scheduling casting lines of an aluminium casting and processing plant. In aluminium processing plants, continuous casting lines are the bottleneck resources, i.e. factory throughput is limited by the amount of aluminium that can be cast. The throughput of a casting line might be increased by minimizing total setup time between jobs. The objective is to minimize setup time on production lines for a given time period while balancing workload between production lines to accommodate potential new orders. A mathematical formulation for scheduling jobs to minimize the total setup time while achieving workload balance between the production lines is presented. Since the casting scheduling problem is an NP-hard problem, even with only one casting line, a four-step algorithm to find good solutions in a reasonable amount of time is proposed. In this process, a set of asymmetric travelling salesman problems is followed by a pairwise exchange heuristic. The proposed procedure is applied to a case study using real casting data.     

Flexible job-shop scheduling/rescheduling in dynamic environment: a hybrid MAS/ACO approach

In real-world manufacturing, disruptions are often encountered during the execution of a predetermined schedule, leading to the degradation of its optimality and feasibility. This study presents a hybrid approach for flexible job-shop scheduling/rescheduling problems under dynamic environment. The approach, coined as ‘HMA’ is a combination of multi-agent system (MAS) negotiation and ant colony optimisation (ACO). A fully distributed MAS structure has been constructed to support the solution-finding process by negotiation among the agents. The features of ACO are introduced into the negotiation mechanism in order to improve the performance of the schedule. Experimental studies have been carried out to evaluate the performance of the approach for scheduling and rescheduling under different types of disruptions. Different rescheduling policies are compared and discussed. The results have shown that the proposed approach is a competitive method for flexible job-shop scheduling/rescheduling for both schedule optimality and computation efficiency.     

A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem

In most real manufacturing environments, schedules are usually inevitable with the presence of various unexpected disruptions. In this paper, a rescheduling method based on the hybrid genetic algorithm and tabu search is introduced to address the dynamic job shop scheduling problem with random job arrivals and machine breakdowns. Because the real-time events are difficult to express and take into account in the mathematical model, a simulator is proposed to tackle the complexity of the problem. A hybrid policy is selected to deal with the dynamic feature of the problem. Two objectives, which are the schedule efficiency and the schedule stability, are considered simultaneously to improve the robustness and the performance of the schedule system. Numerical experiments have been designed to test and evaluate the performance of the proposed method. This proposed method has been compared with some common dispatching rules and meta-heuristic algorithms that have been widely used in the literature. The experimental results illustrate that the proposed method is very effective in various shop-floor conditions.