Scheduling algorithms to minimise the total family flow time for job shops with job families

This paper considers the job scheduling problem in which jobs are grouped into job families, but they are processed individually. The decision variable is the sequence of the jobs assigned to each machine. This type of job shop scheduling can be found in various production systems, especially in remanufacturing systems with disassembly, reprocessing and reassembly shops. In other words, the reprocessing shop can be regarded as the job shop with job families since it performs the operations required to bring parts or sub-assemblies disassembled back to like-new condition before reassembling them. To minimise the deviations of the job completion times within each job family, we consider the objective of minimising the total family flow time. Here, the family flow time implies the maximum among the completion times of the jobs within a job family. To describe the problem clearly, a mixed integer programming model is suggested and then, due to the complexity of the problem, two types of heuristics are suggested. They are: (a) priority rule based heuristics; and (b) meta-heuristics. Computational experiments were performed on a number of test instances and the results show that some priority rule based heuristics are better than the existing ones. Also, the meta-heuristics improve the priority rule based heuristics significantly.     

A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness

This paper addresses a real-life production scheduling problem with identical parallel machines, originating from a plant producing Acrylonitrile-Butadiene-Styrene (ABS) plate products. In the considered practical scheduling problem, ABS plate has some specific specifications and each specification has several different levels. Because there is at least one different level of specification between two ABS plate products, it is necessary to make a set-up adjustment on each machine whenever a switch occurs from processing one ABS plate product to another product. As tardiness leads to extra penalty costs and opportunity losses, the objective of minimising total tardiness has become one of the most important tasks for the schedule manager in the plant. The problem can be classified as an identical parallel machine scheduling problem to minimise the total tardiness. A dispatching rule is proposed for this problem and evaluated by comparing it with the current scheduling method and several existing approaches. Moreover, an iterated greedy-based metaheuristic is developed to further improve the initial solution. The experimental results show that the proposed metaheuristic can perform better than an existing tabu search algorithm, and obtain the optimal solution for small-sized problems and significantly improve the initial solutions for large-sized problems.     

Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops

This study considers the batching and scheduling problem in two-stage hybrid flow shops in which each job with a distinct due-date is processed through two serial production stages, each of which has identical machines in parallel. Under the fundamental trade-off that large batch sizes with less frequent changeovers may reduce setup costs and hence increase machine utilisation, while small batch sizes may reduce job flow times and hence improve scheduling performance, the problem is to determine the number of batches, the batch compositions, the allocation of batches to the parallel machines at each stage, and the sequence of the batches allocated to each machine for the objective of minimising the total job tardiness. A mixed integer programming model is developed for the reduced problem in which the number of batches is given, and then, three iterative algorithms are proposed in which batching and scheduling are done repeatedly until a good solution is obtained. To show the performance of the algorithms, computational experiments were done on a number of test instances, and the results are reported. In particular, we show that the number of batches decreases as the ratio of the batch setup time to the job processing time increases.     

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.     

Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness

This paper studies the problem of scheduling flexible job shops with setup times where the setups are sequence-dependent. The objective is to find the schedule with minimum total tardiness. First, the paper develops a mathematical model in the form of mixed integer linear programming and compares it with the available model in the literature. The proposed model outperforms the available model in terms of both size complexity and computational complexity. Then, an effective metaheuristic algorithm based on iterated local search is proposed and compared with a tabu search and variable neighbourhood search algorithms proposed previously for the same problem. A complete experiment is conducted to evaluate the algorithms for performance. All the results show the superiority of the proposed algorithm against the available ones.     

Minimising total weighted completion time on batch and unary machines with incompatible job families

This paper addresses the problem of scheduling on batch and unary machines with incompatible job families such that the total weighted completion time is minimised. A mixed-integer linear programming model is proposed to solve the problem to optimality for small instances. Tight lower bounds and a 4-approximation algorithm are developed. A constraint programming-based method is also proposed. Numerical results demonstrate that the proposed algorithms can obtain high quality solutions and have a competitive performance. Sensitivity analysis indicates that the performance of the proposed algorithms is also robust on different problem structures.     

Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization

A fast local neighbourhood search (FLNS) algorithm is proposed in this paper to minimise the total flow time in the no-wait flow shop scheduling problem, which is known to be NP-hard for more than two machines. In this work, an unscheduled job sequence is constructed firstly according to the total processing time and standard deviation of jobs on the machines. This job sequence is undergone an initial optimisation using basic neighbourhood search algorithm. Then, an innovative local neighbourhood search scheme is designed to search for the partial neighbourhood in each iterative processing and calculate the neighbourhood solution with an objective increment method. This not only improves the solution quality significantly, but also speeds up the convergence of the solution of the algorithm. Moreover, a probabilistic acceptance criterion is adopted to help our method escape from the local optima. Based on Taillard’s benchmarks, the experimental results show that the proposed FLNS algorithm is superior to major existing algorithms (IHA, IBH_LS, GA-VNS and DHS) in terms of both quality and robustness, and can provide best upper bounds. The in-depth statistical analysis demonstrates that the promising performance of our proposed algorithm is also statistically significant.     

New approximation algorithms for flow shop total completion time problem

This article addresses the flow shop scheduling problem to minimize the sum of the completion times. On the basis of the properties in job sequencing, the triangular shortest processing time (TSPT) first and dynamic triangular shortest processing time first heuristics are designed to solve the static and dynamic versions of this problem, respectively. Moreover, an improvement scheme is provided for these heuristics to enhance the quality of the original solutions. For further numerical evaluation of the heuristics, two new lower bounds with performance guarantees are presented for the two versions of the problem. At the end of the article, a series of numerical experiments is conducted to demonstrate the effectiveness of the algorithms.     

New block properties for flowshop scheduling with blocking and their application in an iterated greedy algorithm

This paper proposes new block properties for the flowshop scheduling problem with blocking to minimise makespan. A pruning procedure based on these proposed properties is used in the construction phase of an iterated greedy algorithm to decrease the total number of solutions to be examined to find an optimal schedule. Computational results using Taillard’s benchmark problem instances show that the new block properties help to eliminate more ‘unpromising’ solutions than the classic properties. In addition, the effectiveness of the proposed algorithm is verified by comparison with some high-performing algorithms for the considered problem.     

An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time

With the increasing attention on environment issues, green scheduling in manufacturing industry has been a hot research topic. As a typical scheduling problem, permutation flow shop scheduling has gained deep research, but the practical case that considers both setup and transportation times still has rare research. This paper addresses the energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time to minimise both makespan as economic objective and energy consumption as green objective. The mathematical model of the problem is formulated. To solve such a bi-objective problem effectively, an improved multi-objective evolutionary algorithm based on decomposition is proposed. With decomposition strategy, the problem is decomposed into several sub-problems. In each generation, a dynamic strategy is designed to mate the solutions corresponding to the sub-problems. After analysing the properties of the problem, two heuristics to generate new solutions with smaller total setup times are proposed for designing local intensification to improve exploitation ability. Computational tests are carried out by using the instances both from a real-world manufacturing enterprise and generated randomly with larger sizes. The comparisons show that dynamic mating strategy and local intensification are effective in improving performances and the proposed algorithm is more effective than the existing algorithms.     

Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns

The job-shop scheduling problem (JSSP) is considered to be one of the most complex combinatorial optimisation problems. In our previous attempt, we hybridised a Genetic Algorithm (GA) with a local search technique to solve JSSPs. In this research, we propose an improved local search technique, Shifted Gap-Reduction (SGR), which improves the performance of GAs when solving relatively difficult test problems. We also modify the new algorithm for JSSPs with machine unavailability and breakdowns. We consider two scenarios of machine unavailability. First, where the unavailability information is available in advance (predictive) and, secondly, where the information is known after a real breakdown (reactive). We show that the revised schedule is mostly able to recover if the interruptions occur during the early stages of the schedules.     

Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data

We consider a total flow time minimisation problem of uniform parallel machine scheduling when job processing times are only known to be bounded within certain given intervals. A minmax regret model is proposed to identify a robust schedule that minimises the maximum deviation from the optimal total flow time over all possible realisations of the job processing times. To solve this problem, we first prove that the maximal regret for any schedule can be obtained in polynomial time. Then, we derive a mixed-integer linear programming (MILP) formulation of our problem by exploiting its structural properties. To reduce the computational time, we further transform our problem into a robust single-machine scheduling problem and derive another MILP formulation with fewer variables and constraints. Moreover, we prove that the optimal schedule under the midpoint scenario is a 2-approximation for our minmax regret problem. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

An immune algorithm for scheduling a hybrid flow shop with sequence-dependent setup times and machines with random breakdowns

Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. Furthermore, most scheduling problems that have been discussed in the literature are under the assumption that machines are continuously available. Nevertheless, in most real-life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to scheduled preventive maintenance where the periods of unavailability are known in advance (deterministic unavailability). This paper deals with hybrid flow shop scheduling problems in which there are sequence-dependent setup times (SDSTs), and machines suffer stochastic breakdowns, to optimise objectives based on the expected makespan. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. An immune algorithm (IA) can be used to tackle complex problems and produce a reasonable manufacturing schedule within an acceptable time. In this research, a computational method based on a clonal selection principle and an affinity maturation mechanism of the immune response is used. This paper describes how we can incorporate simulation into an immune algorithm for the scheduling of a SDST hybrid flow shop with machines that suffer stochastic breakdowns. The results obtained are analysed using a Taguchi experimental design.     

Lagrangian relaxation and cut generation for sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness

The Lagrangian relaxation and cut generation technique is applied to solve sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness. The original problem is decomposed into individual job-level subproblems that can be effectively solved by dynamic programming. Two types of additional constraints for the violation of sequence-dependent setup time constraints are imposed on the decomposed subproblems in order to improve the lower bound. The decomposed subproblem with the additional setup time constraints on any subset of jobs is also effectively solved by a novel dynamic programming. Computational results show that the lower bound derived by the proposed method is much better than those of CPLEX and branch and bound for problem instances with 50 jobs and five stages with less computational effort.     

Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.     

Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions

In this paper, we consider unrelated parallel-machine scheduling involving controllable processing times and rate-modifying activities simultaneously. We assume that the actual processing time of a job can be compressed by allocating a greater amount of a common resource to process the job. We further assume that each machine may require a rate-modifying activity during the scheduling horizon. The objective is to determine the optimal job compressions, the optimal positions of the rate-modifying activities and the optimal schedule to minimise a total cost function that depends on the total completion time and total job compressions. If the number of machines is a given constant, we propose an efficient polynomial time algorithm to solve the problem.     

Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions

This article investigates the criterion of minimizing total k-power completion time (TKCT) in flow shop and open shop scheduling. For these NP-hard problems, the asymptotic optimality of the shortest processing time-based algorithms is proven for a sufficiently large problem scale. To numerically evaluate the convergence of the algorithms, new lower bounds with performance guarantees are presented for the flow shop TKCT problem. Computational results demonstrate the performance of the proposed algorithms and the effectiveness of the nonlinear objective. In addition, theoretical results on the single-machine TKCT problem are obtained for mathematical deduction.