An energy-efficient two-stage hybrid flow shop scheduling problem in a glass production

Energy-efficient scheduling is highly necessary for energy-intensive industries, such as glass, mould or chemical production. Inspired by a real-world glass-ceramics production process, this paper investigates a bi-criteria energy-efficient two-stage hybrid flow shop scheduling problem, in which parallel machines with eligibility are at stage 1 and a batch machine is at stage 2. The performance measures considered are makespan and total energy consumption. Time-of-use (TOU) electricity prices and different states of machines (working, idle and turnoff) are integrated. To tackle this problem, a mixed integer programming (MIP) is formulated, based on which an augmented ε-constraint (AUGMECON) method is adopted to obtain the exact Pareto front. A problem-tailored constructive heuristic method with local search strategy, a bi-objective tabu search algorithm and a bi-objective ant colony optimisation algorithm are developed to deal with medium- and large-scale problems. Extensive computational experiments are conducted, and a real-world case is solved. The results show effectiveness of the proposed methods, in particular the bi-objective tabu search.     

Energy-oriented bi-objective optimisation for a multi-module reconfigurable manufacturing system

This paper investigates a multi-module reconfigurable manufacturing system for multi-product manufacturing. The system consists of a rotary table and multiple machining modules (turrets and spindles). The production plan of the system is divided into the system design phase and the manufacturing phase, where the installation cost and the energy consumption cost correspond to the two phases, respectively. A mixed-integer programming model for a more general problem is presented. The objectives are to minimise the total cost and minimise the cycle time simultaneously. To solve the optimisation problem, the ε-constraint method is adopted to obtain the Pareto front for small size problems. Since the ε-constraint method is time consuming when problem size increases, we develop a multi-objective simulated annealing algorithm for practical size problems. To demonstrate the efficiency of the proposed algorithm, we compare it with a classic non-dominated sorting genetic algorithm. Experimental results demonstrate the efficiency of the multi-objective simulated annealing algorithm in terms of solution quality and computation time.     

Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.     

Augmented ε-constraint method in multi-objective flowshop problem with past sequence set-up times and a modified learning effect

This article addresses a general tri-objective non-permutation flowshop problem to minimise the makespan, the sum of flow time and maximum tardiness simultaneously. In order to enhance the applicability of the model, some practical assumptions are included. These are release dates, past sequence-dependent set-up times, a truncated generalisation of Dejong’s learning effect and predetermined machine availability constraints. First, the problem is formulated as a mixed-integer linear programming model. Second, the true Pareto front is achieved with augmented ε-constraint method for small-sized problems. Third, due to the high complexity of the model and the impractical computational times of larger instances, a heuristic algorithm based on the ε-constraint method is also proposed. Finally, the algorithms are tested to gauge their effectiveness, and the results are compared with other methods.     

A tabu search algorithm for simultaneous machine/AGV scheduling problem

Machines and automated guided vehicles (AGVs) scheduling problems are two essential issues that need to be addressed for the efficiency of the overall production system. The purpose of this paper is to study the simultaneous scheduling problem of machines and AGVs in a flexible manufacturing system (FMS) since the global optimum cannot be reached by considering each of them individually. In this paper, a mixed integer linear programming (MILP) model is developed with the objective of makespan minimisation. The MILP model consists of the following two constraint sets: machines and AGVs scheduling sub-problems. As both sub-problems are known to be NP-hard, a heuristic algorithm based on tabu search (TS) is proposed to get optimal or near to optimal solution for large-size problems within reasonable computation time. The proposed algorithm includes a novel two-dimensional solution representation and the generation of two neighbour solutions, which are alternately and iteratively applied to improve solutions. Moreover, an improved lower bound calculation method is introduced for the large-size problems. Computational results show the superior performance of the TS algorithm for the simultaneous scheduling problem.     

Electroplating production scheduling by cyclogram unfolding in dynamic hoist scheduling problem

This article presents a scheduling problem that exists in electroplating lines. An electroplating line is an automated manufacturing system which covers machine parts with a coat of metal. It consists of a set of tanks that chemically process the items and hoists that transport the items between workstations. Scheduling the movements of these hoists is commonly called a hoist scheduling problem. The most common approaches to the problem are cyclic hoist scheduling problem and dynamic hoist scheduling problem (DHSP). This article presents a DHSP solution method. The method divides the problem into real time and non-real time. Special schedules, called cyclograms, allow minimisation of the length of non-real time calculations. A notion of the problem is introduced, an outline of a scheduling system is presented, as well as the heuristic algorithm itself. The results of the described method, referred to as a cyclogram unfolding method, are compared to several cases available in the literature.     

Minimizing makespan in a two-stage flow shop with parallel batch-processing machines and re-entrant jobs

Against a background of heat-treatment operations in mould manufacturing, a two-stage flow-shop scheduling problem is described for minimizing makespan with parallel batch-processing machines and re-entrant jobs. The weights and release dates of jobs are non-identical, but job processing times are equal. A mixed-integer linear programming model is developed and tested with small-scale scenarios. Given that the problem is NP hard, three heuristic construction methods with polynomial complexity are proposed. The worst case of the new constructive heuristic is analysed in detail. A method for computing lower bounds is proposed to test heuristic performance. Heuristic efficiency is tested with sets of scenarios. Compared with the two improved heuristics, the performance of the new constructive heuristic is superior.     

Multi-product continuous plant scheduling: combination of decomposition,genetic algorithm,and constructive heuristic

We propose a polylithic method for medium-term scheduling of a large-scale industrial plant operating in a continuous mode. The method combines a decomposition approach, a genetic algorithm (GA) and a constructive MILP-based heuristic. In the decomposition, decisions are made at two levels, using the rolling horizon approach. At the upper level, a reduced set of products and the time period is chosen to be considered in the lower level. At the lower level, a short-term scheduling MILP-model with event-based representation is used. A heuristic solution to the lower level problem is found using a constructive Moving Window heuristic guided by a genetic algorithm. The GA is applied for finding efficient utilisation of critical units in the lower level problem. For solving the one unit scheduling problem, a parallel dynamic programming algorithm is proposed. Implementation of the dynamic programming algorithm for a graphics processing unit (GPU) is incorporated in the GA for improving its performance. The experimental study of the proposed method on a real case of a large-scale plant shows a significant improvement of the solution quality and the solving time comparing to the pure decomposition algorithm proposed in the earlier study, and confirmed suitability of the proposed approach for the real-life production scheduling. In particular, the reduction of the number of changeovers and their duration in the obtained solution as well as the CPU time of solving the problem was about 60% using the new approach.     

Multi-objective optimization of a rectangular micro-channel heat sink using the augmented ε-constraint method

ABSTRACT

This article proposes the use of an improved version of the ?-constraint method for the design and optimization of a rectangular micro-channel heat sink. This study aims to optimize the geometric parameters describing the micro-channel, namely its width, its fin width and its depth. The thermal resistance and the pumping power, considered as indicators of the thermal performance, have been approximated by surrogated models based on response surface approximation. The optimization task is formulated as a nonlinear programming problem. This approach has been implemented in GAMS. Sufficient details on both the single-criterion and multi-criteria formulation of the problem have been provided. The implications of the mathematical modelling formulation and the interrelationship between criteria and estimated quantities have been clarified. The use of the augmented ε-constraint method for the multi-objective optimization of a rectangular micro-channel heat sink constitutes the main contribution of this work.     

Production scheduling optimisation with machine state and time-dependent energy costs

The increase of energy costs specially in manufacturing system encourages researchers to pay more attention to energy management in different ways. This paper investigates a non-preemptive single-machine manufacturing environment to reduce total energy costs of a production system. For this purpose, two new mathematical models are presented. The first contribution consists of an improvement of a mathematical formulation proposed in the literature which deals and deals with a scheduling problem at machine level to process the jobs in a predetermined order. The second model focuses on the generalisation of the previous one to deal simultaneously with the production scheduling at machine level as well as job level. So, the initial predetermined fixed sequence assumption is removed. Since this problem is NP-hard, an heuristic algorithm and a genetic algorithm based on the second model are developed to provide good solutions in reasonable computational time. Finally, the effectiveness of the proposed models and optimisation methods have been tested with different numerical experiments. In average, for small size instances which the mathematical model provides a solution in reasonable computational time, a gap of 2.2% for the heuristic and 1.82% for GA are achieved comparing to the exact method’s solution. These results demonstrate the accuracy and efficiency of both proposed algorithms.     

An improved imperialist competitive algorithm based photolithography machines scheduling

Abstract: Photolithography machine is one of the most expensive equipment in semiconductor manufacturing system, and as such is often the bottleneck for processing wafers. This paper focuses on photolithography machines scheduling with the objective of total completion time minimisation. In contrast to classic parallel machines scheduling, it is characterised by dynamical arrival wafers, re-entrant process flows, dedicated machine constraints and auxiliary resources constraints. We propose an improved imperialist competitive algorithm (ICA) within the framework of a rolling horizon strategy for the problem. We develop a variable time interval-based rolling horizon strategy to decide the scheduling point. We address the global optimisation in every local scheduling by proposing a mixed cost function. Moreover, an adaptive assimilation operator and a sociopolitical competition operator are used to prevent premature convergence of ICA to local optima. A chaotic sequence-based local search method is presented to accelerate the rate of convergence. Computational experiments are carried out comparing the proposed algorithm with ILOG CPLEX, dispatching rules and meta-heuristic algorithms in the literature. It is observed that the algorithm proposed shows an excellent behaviour on cycle time minimisation while with a good on time delivery rate and machine utilisation rate.     

Scheduling identical wafer sorting parallel machines with sequence-dependent setup times using an iterated greedy heuristic

Wafer sorting is one of the most critical processes involved in semiconductor device fabrication. This study addresses the wafer sorting scheduling problem (WSSP), with minimisation of total setup time as the primary criterion and minimisation of the number of testers used as the secondary criterion. In view of the strongly NP-hard nature of this problem, a simple and effective iterated greedy heuristic is presented. The performance of the proposed heuristic is empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor. The experimental results show that the proposed heuristic is effective and efficient as compared to the state-of-art algorithms developed for the same problem. It is believed that this study has developed an approach that is easy to comprehend and satisfies the practical needs of wafer sorting.     

Job shop scheduling with a combination of four buffering constraints

In this paper, a new scheduling problem is investigated in order to optimise a more generalised Job Shop Scheduling system with a Combination of four Buffering constraints (i.e. no-wait, no-buffer, limited-buffer and infinite-buffer) called CBJSS. In practice, the CBJSS is significant in modelling and analysing many real-world scheduling systems in chemical, food, manufacturing, railway, health care and aviation industries. Critical problem properties are thoroughly analysed in terms of the Gantt charts. Based on these properties, an applicable mixed integer programming model is formulated and an efficient heuristic algorithm is developed. Computational experiments show that the proposed heuristic algorithm is satisfactory for solving the CBJSS in real time.     

面向医疗器械企业灭菌工艺的不同容量平行机批调度

针对医疗器械企业灭菌工艺生产过程的调度问题,提出面向灭菌工艺的不同容量平行机批调度方法,建立以最小化总延迟时长、最小化总加工能耗和最大化灭菌柜装载率为目标的不同容量平行机批调度模型。并针对模型的求解提出一种改进的NSGA-III算法(Improved NSGA-III,INSGA-III)。为了获得更高质量的批调度解,采用EDT+MLC启发式规则生成INSGA-III初始种群,并设计一种局部搜索策略以改进算法迭代后期的搜索能力。最后,通过算例仿真与传统调度方法进行对比分析,验证了该模型和算法的有效性和可行性。结果表明,该模型和算法较传统调度方法有明显的优势,可为医疗企业实际生产调度提供新思路。     

Integrated optimisation of scheduling and ordering based on semi-finished goods delayed differentiation

The implementation of dynamic ordering policies is becoming increasingly important for the competitiveness of modern manufacturing systems. However, existing models on dynamic ordering pay little attention to production scheduling, which greatly affects the fulfilment of dynamic ordering, especially in complex manufacturing systems. Therefore, it is imperative to establish a new model which integrates both dynamic ordering and production scheduling. Accordingly, a quantitative measurement method for integration is needed. To this end, this paper proposes a semi-finished goods delayed differentiation (SFGDD) model by taking into account integration of the scheduling inventory control and dynamic ordering simultaneously. The objective of this model is to study the relationship between the shop floor inventory and the ordering control based on the semi-finished goods dynamic dispatching mechanism. In addition, the days of inventory (DOI) and a backorder penalty exponential function are developed to quantitatively measure such a relationship. To obtain the optimal results, this paper employs a heuristic genetic algorithm (HGA) with a heuristic encoding scheme to synchronise the generation and selection of inventory variables coherently. A case study on a semiconductor assembly and test manufacturing (ATM) is presented, and a significant revenue enhancement and inventory reduction are achieved accordingly.     

Single-machine scheduling problems with a batch-dependent aging effect and variable maintenance activities

We consider single-machine scheduling problems with a batch-dependent ageing effect and variable maintenance activities between batches. The machine can process several jobs as a batch. It requires maintenance activities where the maintenance time depends on the flow time of the pre-batch, i.e. the batch processed before a batch. A job’s actual processing time is an increasing exponential function of its operation time within a batch. The objectives are to minimise the makespan and the total completion time. We develop polynomial time algorithms for the makespan minimisation problem and the total completion time minimisation problem under the condition that the ageing factor is greater than one. We also provide a mathematical programming approach and two heuristic algorithms to analyse the total completion time minimisation problem when the ageing factor is less than one for even one batch. The computational analysis indicates that the proposed heuristic algorithms are more efficient for the smaller ageing factor, whereas the Modified Shortest Processing Time algorithm is more efficient than the proposed heuristic algorithms for the larger ageing factor.     

Multi-threaded simulated annealing for a bi-objective maintenance scheduling problem

A parallel Simulated Annealing algorithm with multi-threaded architecture is proposed to solve a real bi-objective maintenance scheduling problem with conflicting objectives: the minimisation of the total equipment downtime caused by maintenance jobs and the minimisation of the multi-skilled workforce requirements over the given horizon. The maintenance jobs have different priorities with some precedence relations between different skills. The total weighted flow time is used as a scheduling criterion to measure the equipment availability. The multi-threaded architecture is used to speed up a multi-objective Simulated Annealing algorithm to solve the considered problem. Multi-threading is a form of parallelism based on shared memory architecture where multiple logical processing units, so-called threads, run concurrently and communicate via shared memory. The performance of the parallel method compared to the exact method is verified using a number of test problems. The obtained results imply the high efficiency and robustness of the proposed heuristic for both solution quality and computational effort.     

Re-entrant flow shop scheduling problem with time windows using hybrid genetic algorithm based on auto-tuning strategy

The re-entrant flow shop scheduling problem considering time windows constraint is one of the most important problems in hard-disc drive (HDD) manufacturing systems. In order to maximise the system throughput, the problem of minimising the makespan with zero loss is considered. In this paper, evolutionary techniques are proposed to solve the complex re-entrant scheduling problem with time windows constraint in manufacturing HDD devices with lot size. This problem can be formulated as a deterministic Fm?|?fmls, rcrc, temp?|?C_max problem. A hybrid genetic algorithm was used for constructing chromosomes by checking and repairing time window constraints, and improving chromosomes by a left-shift heuristic as a local search algorithm. An adaptive hybrid genetic algorithm was eventually developed to solve this problem by using fuzzy logic control in order to enhance the search ability of the genetic algorithm. Finally, numerical experiments were carried out to demonstrate the efficiency of the developed approaches.     

A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria

The problem of scheduling in flowshop and flowline-based manufacturing cell is considered with the bicriteria of minimizing makespan and total flowtime of jobs, The formulation of the scheduling problems for both the flowshop and the flowline-based manufacturing cell is first discussed. We then present the development of the proposed heuristic for flowshop scheduling. A heuristic preference relation is developed as the basis for the heuristic so that only the potential job interchanges are checked for possible improvement with respect to bicriteria, The proposed heuristic algorithm as well as the existing heuristic are evaluated in a large number of randomly generated large-sized flowshop problems. We also investigate the effectiveness of these heuristics with respect to the objective of minimizing total machine idletime. We then modify the proposed heuristic for scheduling in a cell, and evaluate its performance.     

A multi-level heuristic search algorithm for production scheduling

This paper introduces a multi-level heuristic search algorithm for identifying the optimal production schedule considering different levels of manufacturing requirements and constraints. The multi-level heuristic search algorithm generates search nodes at different levels. An upper level search node is composed of lower level search nodes, and evaluated based upon the evaluation of these lower level search nodes using a heuristic function. A production scheduling system was developed based upon the multi-level heuristic search algorithm. In this scheduling system, production requirements and constraints are represented at three different levels: task level, process level, and resource level. A task describes a manufacturing requirement. A process defines a method to achieve the goal of a task. A resource, such as a machine or a person, is a facility for accomplishing a required process. The multi-level heuristic search-based scheduling system was implemented using Smalltalk, an object-oriented programming language. Discussions on scheduling quality and efficiency are addressed at the end of this paper.