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.     

Bi-objective reentrant hybrid flowshop scheduling: an iterated Pareto greedy algorithm

The multi-objective reentrant hybrid flowshop scheduling problem (RHFSP) exhibits significance in many industrial applications, but appears under-studied in the literature. In this study, an iterated Pareto greedy (IPG) algorithm is proposed to solve a RHFSP with the bi-objective of minimising makespan and total tardiness. The performance of the proposed IPG algorithm is evaluated by comparing its solutions to existing meta-heuristic algorithms on the same benchmark problem set. Experimental results show that the proposed IPG algorithm significantly outperforms the best available algorithms in terms of the convergence to optimal solutions, the diversity of solutions and the dominance of solutions. The statistical analysis manifestly shows that the proposed IPG algorithm can serve as a new benchmark approach for future research on this extremely challenging scheduling problem.     

A bi-objective parallel machine problem with eligibility,release dates and delivery times of the jobs

The scheduling of parallel machines is a well-known problem in many companies. Nevertheless, not always all the jobs can be manufactured in any machine and the eligibility appears. Based on a real-life problem, we present a model which has m parallel machines with different level of quality from the highest level for the first machine till the lowest level for the last machine. The set of jobs to be scheduled on these m parallel machines are also distributed among these m levels: one job from a level can be manufactured in a machine of the same or higher level but a penalty, depending on the level, appears when a job is manufactured in a machine different from the highest level i.e. different from the first machine. Besides, there are release dates and delivery times associated to each job. The tackled problem is bi-objective with the criteria: minimisation of the final date – i.e. the maximum for all the jobs of their completion time plus the delivery time – and the minimisation of the total penalty generated by the jobs. In a first step, we analyse the sub-problem of minimisation of the final date on a single machine for jobs with release dates and delivery times. Four heuristics and an improvement algorithm are proposed and compared on didactic examples and on a large set of instances. In a second step an algorithm is proposed to approximate the set of efficient solutions and the Pareto front of the bi-objective problem. This algorithm contains two phases: the first is a depth search phase and the second is a backtracking phase. The procedure is illustrated in detail on an instance with 20 jobs and 3 machines. Then extensive numerical experiments are realised on two different sets of instances, with 20, 30 and 50 jobs, 3 or 4 machines and various values of penalties. Except for the case of 50 jobs, the results are compared with the exact Pareto front.     

Bi-objective cyclic scheduling in a robotic cell with processing time windows and non-Euclidean travel times

This paper addresses bi-objective cyclic scheduling in a robotic cell with processing time windows. In particular, we consider a more general non-Euclidean travel time metric where robot’s travel times are not required to satisfy the well-known triangular inequality. We develop a tight bi-objective mixed integer programming (MIP) model with valid inequalities for the cyclic robotic cell scheduling problem with processing time windows and non-Euclidean travel times. The objective is to minimise the cycle time and the total robot travel distance simultaneously. We propose an iterative ε-constraint method to solve the bi-objective MIP model, which can find the complete Pareto front. Computational results both on benchmark instances and randomly generated instances indicate that the proposed approach is efficient in solving the cyclic robotic cell scheduling problems.     

Improved mixed-integer linear programming model and heuristics for bi-objective single-machine batch scheduling with energy cost consideration

This article addresses bi-objective single-machine batch scheduling under time-of-use electricity prices to minimize the total energy cost and the makespan. The lower and upper bounds on the number of formed batches are first derived and a continuous-time mixed-integer linear programming model is proposed, which improves an existing discrete-time model in the literature. Two improved heuristics are proposed based on the improved model. Computational experiments demonstrate that the improved model and heuristics can run hundreds of times faster than the existing ones for large-size instances.     

Coordinating strategic outsourcing decisions for semiconductor assembly using a bi-objective genetic algorithm

Increasing global competition has forced high-tech companies to focus on their core competences and outsource other activities to maintain their competitive advantages in the supply chains. While most companies rely on domain experts to coordinate strategic outsourcing decisions among a number of qualified vendors with different capabilities, the present problem can be formulated into a complex nonlinear, multi-dimensional, multi-objective combinatorial optimisation problem. Focused on real settings, this study aims to fill the gap via developing a bi-objective genetic algorithm (boGA) for determining the outsourcing order allocation with nonlinear cost structure, while minimising both the total alignment gap and the total allocation cost. The proposed boGA incorporates specific random key representation to facilitate encoding and decoding. This study also develops a bi-objective Pareto solution generation algorithm to enable efficient searching of Pareto solutions in multiple ranks and designs a composite Pareto ranking selection with uniform sum rank weighting for effective selection. To estimate its validity, the proposed boGA was validated with realistic cases from a leading semiconductor company in Hsinchu Science Park in Taiwan. The optimal boGA parameters were tested using a set of experiments. Scenario analyses were conducted to evaluate the performance of the proposed algorithm under different demand conditions using the metrics in the literature. The results have shown the practical viability of the proposed algorithm to solve the present problem of monthly outsourcing decisions for the case company in practicable computation time. This algorithm can determine the near-optimal Pareto front for decision makers to further incorporate with their preferences. This study concludes with discussion of future research directions.     

Modelling and optimization of a bi-objective flow shop scheduling with diverse maintenance requirements

In real-world problems, machines cannot continuously operate and have to stop for maintenance before they fail. Lack of maintenance can also affect the performance of machines in processing jobs. In this paper, a permutation flow shop scheduling problem with multiple age-based maintenance requirements is modelled as a novel mixed-integer linear program in which the objectives are conflicting. In modelling the problem, we assume that infrequent maintenance can prolong job processing times. One of the objectives is to minimise the total maintenance cost by planning as few maintenance activities as possible to only meet the minimum requirements, and the other objective tries to minimise the total tardiness by sequencing the jobs and planning the maintenance activities in such a way that the processing times are not prolonged and unnecessary maintenance times are avoided. Because of this conflict, an interactive fuzzy, bi-objective model is introduced. Application of the model is illustrated through a case study for operations and maintenance scheduling of heavy construction machinery. An effective and efficient solution methodology is developed based on the structure of the problem and tested against commercial solvers and a standard GA. Computational results have verified the efficiency of the proposed solution methodology and show that unlike the proposed method, a generic metaheuristic that does not consider the unique structure of the problem can become ineffective for real-world problem sizes.     

Multi-objective genetic algorithm for solving N-version program design problem

N-version programming (NVP) is a programming approach for constructing fault tolerant software systems. Generally, an optimization model utilized in NVP selects the optimal set of versions for each module to maximize the system reliability and to constrain the total cost to remain within a given budget. In such a model, while the number of versions included in the obtained solution is generally reduced, the budget restriction may be so rigid that it may fail to find the optimal solution. In order to ameliorate this problem, this paper proposes a novel bi-objective optimization model that maximizes the system reliability and minimizes the system total cost for designing N-version software systems. When solving multi-objective optimization problem, it is crucial to find Pareto solutions. It is, however, not easy to obtain them. In this paper, we propose a novel bi-objective optimization model that obtains many Pareto solutions efficiently.We formulate the optimal design problem of NVP as a bi-objective 0–1 nonlinear integer programming problem. In order to overcome this problem, we propose a Multi-objective genetic algorithm (MOGA), which is a powerful, though time-consuming, method to solve multi-objective optimization problems. When implementing genetic algorithm (GA), the use of an appropriate genetic representation scheme is one of the most important issues to obtain good performance. We employ random-key representation in our MOGA to find many Pareto solutions spaced as evenly as possible along the Pareto frontier. To pursue improve further performance, we introduce elitism, the Pareto-insertion and the Pareto-deletion operations based on distance between Pareto solutions in the selection process.The proposed MOGA obtains many Pareto solutions along the Pareto frontier evenly. The user of the MOGA can select the best compromise solution among the candidates by controlling the balance between the system reliability and the total cost.     

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.     

Discrete harmony search algorithm for scheduling and rescheduling the reprocessing problems in remanufacturing: a case study

In this article, scheduling and rescheduling problems with increasing processing time and new job insertion are studied for reprocessing problems in the remanufacturing process. To handle the unpredictability of reprocessing time, an experience-based strategy is used. Rescheduling strategies are applied for considering the effect of increasing reprocessing time and the new subassembly insertion. To optimize the scheduling and rescheduling objective, a discrete harmony search (DHS) algorithm is proposed. To speed up the convergence rate, a local search method is designed. The DHS is applied to two real-life cases for minimizing the maximum completion time and the mean of earliness and tardiness (E/T). These two objectives are also considered together as a bi-objective problem. Computational optimization results and comparisons show that the proposed DHS is able to solve the scheduling and rescheduling problems effectively and productively. Using the proposed approach, satisfactory optimization results can be achieved for scheduling and rescheduling on a real-life shop floor.     

A new heuristic for the flowshop scheduling problem to minimize makespan and maximum tardiness

This paper presents a new heuristic for solving the flowshop scheduling problem that aims to minimize makespan and maximize tardiness. The algorithm is able to take into account the aforementioned performance measures, finding a set of non-dominated solutions representing the Pareto front. This method is based on the integration of two different techniques: a multi-criteria decision-making method and a constructive heuristic procedure developed for makespan minimization in flowshop scheduling problems. In particular, the technique for order preference by similarity of ideal solution (TOPSIS) algorithm is integrated with the Nawaz–Enscore–Ham (NEH) heuristic to generate a set of potential scheduling solutions. To assess the proposed heuristic's performance, comparison with the best performing multi-objective genetic local search (MOGLS) algorithm proposed in literature is carried out. The test is executed on a large number of random problems characterized by different numbers of machines and jobs. The results show that the new heuristic frequently exceeds the MOGLS results in terms of both non-dominated solutions, set quality and computational time. In particular, the improvement becomes more and more significant as the number of jobs in the problem increases.     

Bi-objective mathematical model and improved algorithm for optimisation of welding shop scheduling problem

This paper addresses a bi-objective welding shop scheduling problem (BWSSP) aiming to minimise the total tardiness and the machine interaction effect. The BWSSP is a special flow-shop scheduling problem (FSP) which is characterised by the fact that more than one machine can process on one job at a certain stage. This study analyses the operation of a structural metal manufacturing plant, and includes various aspects such as job sequence, machine-number-dependent processing time, lifting up time, lifting down time and different delivery time. A novel mixed-integer programming model (MIPM) is established, which can be used to minimise the delayed delivery time and the total machine interaction effect. One machine interaction effect formula is given in this paper. In order to solve this BWSSP, an appropriate non-dominated sorting Genetic Algorithm III (NSGAIII), embedded with a restarted strategy (RNSGAIII), is proposed. The restarted strategy, which can increase the diversity of the solutions, will be triggered with a restart probability. Following the iterative process, an effective strategy is applied to reduce the interaction effect penalty, on the premise that the makespan will remain unchanged. Total five algorithms, namely NSGAII, NSGAIII, harmony search algorithm (HSA), strength Pareto evolutionary algorithm (SPEA2), and RNSGAIII are utilised to solve this engineering problem. Numerical simulations show that the improved RNSGAIII outperforms the other methods, and the Pareto solution distribution and diversity, in particular, are significantly improved.     

A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems

This paper presents a hybrid Pareto-based local search (PLS) algorithm for solving the multi-objective flexible job shop scheduling problem. Three minimisation objectives are considered simultaneously, i.e. the maximum completion time (makespan), the total workload of all machines, and the workload of the critical machine. In this study, several well-designed neighbouring approaches are proposed, which consider the problem characteristics and thus can hold fast convergence ability while keep the population with a certain level of quality and diversity. Moreover, a variable neighbourhood search (VNS) based self-adaptive strategy is embedded in the hybrid algorithm to utilise the neighbouring approaches efficiently. Then, an external Pareto archive is developed to record the non-dominated solutions found so far. In addition, a speed-up method is devised to update the Pareto archive set. Experimental results on several well-known benchmarks show the efficiency of the proposed hybrid algorithm. It is concluded that the PLS algorithm is superior to the very recent algorithms, in term of both search quality and computational efficiency.     

A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness

This paper considers the problem of scheduling jobs in a permutation flow shop with the objective of minimising total earliness and tardiness. A genetic algorithm is proposed for the problem. This procedure and five other procedures were tested on problem sets that varied in terms of number of jobs, machines and the tightness and range of due dates. It was found that the genetic algorithm procedure was consistently effective in generating good solutions relative to the other procedures.     

Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes

This paper considers the parallel batch processing machine scheduling problem which involves the constraints of unequal ready times, non-identical job sizes, and batch dependent processing times in order to sequence batches on identical parallel batch processing machines with capacity restrictions. This scheduling problem is a practical generalisation of the classical parallel batch processing machine scheduling problem, which has many real-world applications, particularly, in the aging test operation of the module assembly stage in the manufacture of thin film transistor liquid crystal displays (TFT-LCD). The objective of this paper is to seek a schedule with a minimum total completion time for the parallel batch processing machine scheduling problem. A mixed integer linear programming (MILP) model is proposed to optimise the scheduling problem. In addition, to solve the MILP model more efficiently, an effective compound algorithm is proposed to determine the number of batches and to apply this number as one parameter in the MILP model in order to reduce the complexity of the problem. Finally, three efficient heuristic algorithms for solving the large-scale parallel batch processing machine scheduling problem are also provided.     

Integrated scheduling and self-reconfiguration for assembly job shop in knowledgeable manufacturing

The problems of integrated assembly job shop (AJS) scheduling and self-reconfiguration in knowledgeable manufacturing are studied with the objective of minimising the weighted sum of completion cost of products, the earliness penalty of operations and the training cost of workers. In AJS, each workstation consists of a certain number of teams of workers. A product is assumed to have a tree structure consisting of components and subassemblies. The assembly of components, subassemblies and final products are optimised with the capacity of workstations simultaneously. A heuristic algorithm is developed to solve the problem. Dominance relations of operations are derived and applied in the development of the heuristic. A backward insertion search strategy is designed to locally optimise the operation sequence. Once the optimal schedule is acquired, the teams are reconfigured by transferring them from workstations of lower utilisation to those of higher utilisation. Effectiveness of the proposed algorithm is tested by a number of numerical experiments. The results show that the proposed algorithm promises lower total cost and desirable simultaneous self-reconfiguration in accordance with scheduling.     

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.     

Simultaneous scheduling of production and maintenance tasks in the job shop

This paper deals with the job shop problem of simultaneous scheduling of production operations and preventive maintenance tasks. To solve this problem, we develop an elitist multi-objective genetic algorithm that provides a set of Pareto optimal solutions minimising the makespan and the total maintenance cost. A deep study was made to choose the best encoding, operators, and the different probabilities. Some lower bounds of the adopted criteria are developed. The computational experiments carried out on a set of published instances validate the efficiency of the proposed algorithm.     

Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method

This paper investigates an integrated bi-objective optimisation problem with non-resumable jobs for production scheduling and preventive maintenance in a two-stage hybrid flow shop with one machine on the first stage and m identical parallel machines on the second stage. Sequence-dependent set-up times and preventive maintenance (PM) on the first stage machine are considered. The scheduling objectives are to minimise the unavailability of the first stage machine and to minimise the makespan simultaneously. To solve this integrated problem, three decisions have to be made: determine the processing sequence of jobs on the first stage machine, determine whether or not to perform PM activity just after each job, and specify the processing machine of each job on the second stage. Due to the complexity of the problem, a multi-objective tabu search (MOTS) method is adapted with the implementation details. The method generates non-dominated solutions with several parallel tabu lists and Pareto dominance concept. The performance of the method is compared with that of a well-known multi-objective genetic algorithm, in terms of standard multi-objective metrics. Computational results show that the proposed MOTS yields a better approximation.     

Parallel machine scheduling with limited controllable machine availability

Most machine scheduling models assume that either the machines are available all the time, or the time of their unavailability is fixed as a constraint. In this paper, we study the problem that neither the unavailability length nor the start time of machine unavailability is fixed. Instead, they would be determined in order to minimise the total cost involved with the completion time and the unavailable time. This model could represent a more realistic and complex situation, in which jobs and machines’ availability operations should be optimised simultaneously. After the model is formulated, some properties of the problem are presented. Then a branch and bound algorithm based on column generation approach is proposed to solve the problem. The computation results show that, within a reasonable computation time, the proposed algorithm can solve medium sized problems optimally.