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.     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.     

Bottleneck-based heuristics to minimize tardy jobs in a flexible flow line with unrelated parallel machines

This paper develops new bottleneck-based heuristics with machine selection rules to solve the flexible flow line problem with unrelated parallel machines in each stage and a bottleneck stage in the flow line. The objective is to minimize the number of tardy jobs in the problem. The heuristics consist of three steps: (1) identifying the bottleneck stage; (2) scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage; (3) using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule the jobs on the bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at the bottleneck stage. In order to evaluate the performance of the proposed heuristics, six well-known dispatching rules are examined for comparison purposes. Six factors are used to design 729 production scenarios, and ten test problems are generated for each scenario. Computational results show that the proposed heuristics significantly outperform all the well-known dispatching rules. An analysis of the experimental factors is also performed and several interesting insights into the heuristics are discovered.     

A discrete artificial bee colony algorithm for single machine scheduling problems

This paper presents a discrete artificial bee colony algorithm for a single machine earliness–tardiness scheduling problem. The objective of single machine earliness–tardiness scheduling problems is to find a job sequence that minimises the total sum of earliness–tardiness penalties. Artificial bee colony (ABC) algorithm is a swarm-based meta-heuristic, which mimics the foraging behaviour of honey bee swarms. In this study, several modifications to the original ABC algorithm are proposed for adapting the algorithm to efficiently solve combinatorial optimisation problems like single machine scheduling. In proposed study, instead of using a single search operator to generate neighbour solutions, random selection from an operator pool is employed. Moreover, novel crossover operators are presented and employed with several parent sets with different characteristics to enhance both exploration and exploitation behaviour of the proposed algorithm. The performance of the presented meta-heuristic is evaluated on several benchmark problems in detail and compared with the state-of-the-art algorithms. Computational results indicate that the algorithm can produce better solutions in terms of solution quality, robustness and computational time when compared to other algorithms.     

A differential evolution algorithm for the no-idle flowshop scheduling problem with total tardiness criterion

In this paper, we investigate the use of a continuous algorithm for the no-idle permutation flowshop scheduling (NIPFS) problem with tardiness criterion. For this purpose, a differential evolution algorithm with variable parameter search (vpsDE) is developed to be compared to a well-known random key genetic algorithm (RKGA) from the literature. The motivation is due to the fact that a continuous DE can be very competitive for the problems where RKGAs are well suited. As an application area, we choose the NIPFS problem with the total tardiness criterion in which there is no literature on it to the best of our knowledge. The NIPFS problem is a variant of the well-known permutation flowshop (PFSP) scheduling problem where idle time is not allowed on machines. In other words, the start time of processing the first job on a given machine must be delayed in order to satisfy the no-idle constraint. The paper presents the following contributions. First of all, a continuous optimisation algorithm is used to solve a combinatorial optimisation problem where some efficient methods of converting a continuous vector to a discrete job permutation and vice versa are presented. These methods are not problem specific and can be employed in any continuous algorithm to tackle the permutation type of optimisation problems. Secondly, a variable parameter search is introduced for the differential evolution algorithm which significantly accelerates the search process for global optimisation and enhances the solution quality. Thirdly, some novel ways of calculating the total tardiness from makespan are introduced for the NIPFS problem. The performance of vpsDE is evaluated against a well-known RKGA from the literature. The computational results show its highly competitive performance when compared to RKGA. It is shown in this paper that the vpsDE performs better than the RKGA, thus providing an alternative solution approach to the literature that the RKGA can be well suited.     

SCHEDULING A SINGLE MACHINE TO MINIMIZE TWO CRITERIA: MAXIMUM TARDINESS AND NUMBER OF TARDY JOBS

In this paper we consider a single machine scheduling problem with two criteria; minimizing both maximum tardiness and the number of tardy jobs. We present both heuristic and branch-and-bound algorithms to find the schedule which minimizes the number of tardy jobs among all schedules having minimal maximum tardiness. Computational results show that problems with up to 40 jobs can be solved in less than one minute of computer time, and solution difficulty tends to increase as the range of due dates increases relative to the total processing time. We extend our results to generate all nondominated schedules for the two criteria. Computational experiments indicate that all non-dominated solutions to problems with 40 jobs can be generated. However, solution difficulty for these problems is highly dependent on problem parameters.     

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.     

Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times

This paper focuses on an identical parallel machine scheduling problem with minimising total tardiness of jobs. There are two major issues involved in this scheduling problem; (1) jobs which can be split into multiple sub-jobs for being processed on parallel machines independently and (2) sequence-dependent setup times between the jobs with different part types. We present a novel mathematical model with meta-heuristic approaches to solve the problem. We propose two encoding schemes for meta-heuristic solutions and three decoding methods for obtaining a schedule from the meta-heuristic solutions. Six different simulated annealing algorithms and genetic algorithms, respectively, are developed with six combinations of two encoding schemes and three decoding methods. Computational experiments are performed to find the best combination from those encoding schemes and decoding methods. Our findings show that the suggested algorithm provides not only better solution quality, but also less computation time required than the commercial optimisation solvers.     

A multi-phase covering Pareto-optimal front method to multi-objective parallel machine scheduling

This paper considers the problem of parallel machine scheduling with sequence-dependent setup times to minimise both makespan and total earliness/tardiness in the due window. To tackle the problem considered, a multi-phase algorithm is proposed. The goal of the initial phase is to obtain a good approximation of the Pareto-front. In the second phase, to improve the Pareto-front, non-dominated solutions are unified to constitute a big population. In this phase, based on the local search in the Pareto space concept, three multi-objective hybrid metaheuristics are proposed. Covering the whole set of Pareto-optimal solutions is a desired task of multi-objective optimisation methods. So in the third phase, a new method using an e-constraint hybrid metaheuristic is proposed to cover the gaps between the non-dominated solutions and improve the Pareto-front. Appropriate combinations of multi-objective methods in various phases are considered to improve the total performance. The multi-phase algorithm iterates over a genetic algorithm in the first phase and three hybrid metaheuristics in the second and third phases. Experiments on the test problems with different structures show that the multi-phase method is a better tool to approximate the efficient set than the global archive sub-population genetic algorithm presented previously.     

Bi-objective optimisation for integrated scheduling of single machine with setup times and preventive maintenance planning

This paper deals with an integrated bi-objective optimisation problem for production scheduling and preventive maintenance in a single-machine context with sequence-dependent setup times. To model its increasing failure rate, the time to failure of the machine is subject to Weibull distribution. The two objectives are to minimise the total expected completion time of jobs and to minimise the maximum of expected times of failure of the machine at the same time. During the setup times, preventive maintenance activities are supposed to be performed simultaneously. Due to the assumption of non-preemptive job processing, three resolution policies are adapted to deal with the conflicts arising between job processing and maintenance activities. Two decisions are to be taken at the same time: find the permutation of jobs and determine when to perform the preventive maintenance. To solve this integrated problem, two well-known evolutionary genetic algorithms are compared to find an approximation of the Pareto-optimal front, in terms of standard multi-objective metrics. The results of extensive computational experiments show the promising performance of the adapted algorithms.     

Workload control and optimised order release: an assessment by simulation

An important scheduling function of manufacturing systems is controlled order release. While there exists a broad literature on order release, reported release procedures typically use simple sequencing rules and greedy heuristics to determine which jobs to select for release. While this is appealing due to its simplicity, its adequateness has recently been questioned. In response, this study uses an integer linear programming model to select orders for release to the shop floor. Using simulation, we show that optimisation has the potential to improve performance compared to ‘classical’ release based on pool sequencing rules. However, in order to also outperform more powerful pool sequencing rules, load balancing and timing must be considered at release. Existing optimisation-based release methods emphasise load balancing in periods when jobs are on time. In line with recent advances in Workload Control theory, we show that a better percentage tardy performance can be achieved by only emphasising load balancing when many jobs are urgent. However, counterintuitively, emphasising urgency in underload periods leads to higher mean tardiness. Compared to previous literature we further highlight that continuous optimisation-based release outperforms periodic optimisation-based release. This has important implications on how optimised-based release should be designed.     

Dispatching rules for scheduling in assembly jobshops - Part 2

In this part of the paper, we present the development and evaluation of dispatching rules for scheduling in jobshops manufacturing multi-level assembly jobs with the performance measures reated to tardiness. We present a new definition of 'operation due date' in the context of assembly jobs and use it in the development of dispatching rules. A simulation study is carried out to evaluate the performances of the existing and the proposed dispatching rules with respect to different measures of tardiness. We also measure their performances with respect to different measures of flowtime and staging delays. The results of the study indicate that the proposed rules perform better than the existing rules.     

Scheduling about an unrestricted common due windowwith arbitrary earliness/tardiness penalty rates

We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due window to minimize total weighted earliness and tardiness cost. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. Earliness or tardiness cost is assessed when a job completes outside the due window, which may be an instant in time or a time increment defining acceptable job completion. In this paper we present properties that characterize the structure of an optimal schedule, present a lower bound, propose a two-step branch and bound algorithm, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized problem instances.     

Scheduling with shutdowns and sequence dependent set-up times

This paper considers a single machine scheduling problem with ready and due times constraints on jobs, shutdown constraints on the machine and sequence dependent set-up times among jobs. The shutdown is a disruptive event such as holiday, breaks or machine maintenance, and has a prespecified period when the machine will be interrupted. If no pre-emption is allowed for jobs, shutdown constraints divide the planning horizon into disconnected time windows. An optimization algorithm based on the branch-and-bound method is developed to minimize the maximum tardiness for solving the problem. This paper further develops the post-processing algorithm that manipulates the starting time of the shutdown period so as to reduce the obtained maximum tardiness. The post-processing algorithm can determine plural schedules to reduce the maximum tardiness, and the production manager will select the objective schedule among them for the interest of overall efficiency. Computational results for the proposed algorithms will indicate that the post-processing algorithm can improve upon the original solution and the problems with multiple shutdowns and with set-up times varying widely can be satisfactorily solved.     

An evolutionary algorithm for a new multi-objective location-inventory model in a distribution network with transportation modes and third-party logistics providers

This paper proposes a multi-objective optimisation algorithm for solving the new multi-objective location-inventory problem (MOLIP) in a distribution centre (DC) network with the presence of different transportation modes and third-party logistics (3PL) providers. 3PL is an external company that performs all or part of a company’s logistics functions. In order to increase the efficiency and responsiveness in a supply chain, it is assumed that 3PL is responsible to manage inventory in DCs and deliver products to customers according to the provided plan. DCs are determined so as to simultaneously minimise three conflicting objectives; namely, total costs, earliness and tardiness, and deterioration rate. In this paper, a non-dominated sorting genetic algorithm (NSGA-II) is proposed to perform high-quality search using two-parallel neighbourhood search procedures for creating initial solutions. The potential of this algorithm is evaluated by its application to the numerical example. Then, the obtained results are analysed and compared with multi-objective simulated annealing (MOSA). It is concluded that this algorithm is capable of generating a set of alternative DCs considering the optimisation of multiple objectives, significantly improving the decision-making process involved in the distribution network design.     

Minimizing earliness–tardiness on a single burn-in oven with a common due date and maximum allowable tardiness constraint

This paper considers a scheduling problem for a single burn-in oven in the semiconductor manufacturing industry where the oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs under the constraint that the maximum tardiness should be less than or equal to the maximum allowable time value. We suggest several two-phase heuristic algorithms for this problem. In the first phase, some heuristic algorithms are developed without maximum allowable tardiness constraint. If the schedule from the first phase violates the maximum tardiness constraint, then the schedule is changed to satisfy maximum allowable tardiness constraint in the second phase. The suggested heuristics are based on genetic algorithms and dominance properties of optimal schedules. We present the results of computational experiments that clearly show the solution quality obtained by the suggested heuristics.     

Scheduling in dynamic assembly job-shops with jobs having different holding and tardiness costs

Most studies on scheduling in dynamic job-shops assume that the holding cost of a job is given by the flowtime of the job and that the tardiness cost of a job is given by the tardiness of the job. In other words, unit holding and unit tardiness costs of a job are assumed. However, in reality, such an assumption need not hold, and it is quite possible that there are different costs for holding and tardiness for different jobs. In addition, most studies on job-shop scheduling assume that jobs are independent and that no assembly operations exist. The current study addresses the problem of scheduling in dynamic assembly job-shops (manufacturing multilevel jobs) with the consideration of different holding and tardiness costs for different jobs. An attempt is made to develop efficient dispatching rules by incorporating the relative costs of holding and tardiness of jobs in the form of scalar weights. The primary objective of scheduling considered here is the minimization of the total scheduling cost consisting of the sum of holding and tardiness costs. The performance of the scheduling rules in minimizing the individual components of total scheduling cost is also observed. The results of an extensive simulation study on the performance of different dispatching rules show that the proposed rules are effective in minimizing the means and maximums of the primary measure, and are quite robust with respect to different job structures and experimental settings.     

Minimisation of total tardiness for identical parallel machine scheduling using genetic algorithm

In recent years research on parallel machine scheduling has received an increased attention. This paper considers minimisation of total tardiness for scheduling of n jobs on a set of m parallel machines. A spread-sheet-based genetic algorithm (GA) approach is proposed for the problem. The proposed approach is a domain-independent general purpose approach, which has been effectively used to solve this class of problem. The performance of GA is compared with branch and bound and particle swarm optimisation approaches. Two set of problems having 20 and 25 jobs with number of parallel machines equal to 2, 4, 6, 8 and 10 are solved with the proposed approach. Each combination of number of jobs and machines consists of 125 benchmark problems; thus a total for 2250 problems are solved. The results obtained by the proposed approach are comparable with two earlier approaches. It is also demonstrated that a simple GA can be used to produce results that are comparable with problem-specific approach. The proposed approach can also be used to optimise any objective function without changing the basic GA routine.     

Single CNC machine scheduling with controllable processing times and multiple due dates

In this study, we solve the single CNC machine scheduling problem with controllable processing times. Our objective is to maximize the total profit that is composed of the revenue generated by the set of scheduled jobs minus the sum of total weighted earliness and weighted tardiness, tooling and machining costs. Customers offer multiple due dates to the manufacturer, each coming with a distinct price for the order that is decreasing as the date gets later, and the manufacturer has the flexibility to accept or reject the orders. We propose a number of ranking rules and scheduling algorithms that we employ in a four-stage heuristic algorithm that determines the processing times for each job and a final schedule for the accepted jobs simultaneously, to maximize the overall profit.     

Fuzzy-metaheuristic methods to solve a hybrid flow shop scheduling problem with pre-assignment

This paper deals with a particular version of the hybrid flow shop scheduling problem inspired from a real application in the automotive industry. Specific constraints such as pre-assigned jobs, non-identical parallel machines and non-compatibility between certain jobs and machines are considered in order to minimise the total tardiness time. A mixed-integer programming model that incorporates these aspects is developed and solved using ILOG Cplex software. Thus, because of the computation time constraint, we propose approximate resolution methods based on genetic and particle swarm optimisation algorithms coupled or not with fuzzy logic control. The effectiveness of these methods is investigated via computational experiments based on theoretical and real case instances. The obtained results show that fuzzy logic control improves the performances of both genetic and particle swarm optimisation algorithms significantly.