Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions

The block erection problem is defined as a parallel machine scheduling problem with precedence constraints and machine eligibility restrictions. A heuristic algorithm combined of the largest total amount of processing first rule (LTAP) and the enhanced smallest machine load first rule (ESML) is proposed to minimise makespan for the block erection in a shipyard. Finally, four lower bounds and the percentage of the reduced makespan compared with the current solutions are defined to evaluate the performance of the proposed algorithm. The experiments are performed on data selected from a shipbuilding company, and the results demonstrate that the presented algorithm can effectively find a good solution to minimise the makespan of the block erection problem.     

Solving the blocking flow shop scheduling problem with makespan using a modified fruit fly optimisation algorithm

The flow shop scheduling problem with blocking has important applications in a variety of industrial systems but is under-represented in the research literature. In this paper, a modified fruit fly optimisation (MFFO) algorithm is proposed to solve the above scheduling problem for makespan minimisation. The MFFO algorithm mainly contains three key operators. One is related to the initialisation scheme in which a problem-specific heuristic is adopted to generate an initial fruit fly swarm location with high quality. The second is concerned with the smell-based search in which a neighbourhood strategy is designed to generate a new location. To further enhance the exploitation of the proposed algorithm considered, a speed-up insert-neighbourhood-based local search is applied with a probability. Finally, the last is for the vision-based search in which an update criterion is proposed to induce the fruit fly into a better searching space. The simulation experimental results demonstrated the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. Moreover, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.     

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.     

Ant colony optimisation with random selection for block transportation scheduling with heterogeneous transporters in a shipyard

This paper considers a scheduling problem of heterogeneous transporters for pickup and delivery blocks in a shipyard assuming a static environment where all transportation requirements for blocks are predetermined. In the block transportation scheduling problem, the important issue is to determine which transporter delivers the block from one plant to the other plant and when, in order to minimise total logistic times. Therefore, the objective of the problem is to simultaneously determine the allocation policy of blocks and the sequence policy of transporters to minimise the weighted sum of empty transporter travel times, delay times, and tardy times. A mathematical model for the optimal solution is derived and an ant colony optimisation algorithm with random selection (ACO_RS) is proposed. To demonstrate the performance of ACO_RS, computational experiments are implemented in comparing the solution with the optimal solutions obtained by CPLEX in small-sized problems and the solutions obtained by conventional ACO in large-sized problems.     

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.     

Improved imperialist competitive algorithms for rebalancing multi-objective two-sided assembly lines with space and resource constraints

In this paper, a mathematical model and an improved imperial competition algorithm (IICA) are proposed to solve the multi-objective two-sided assembly line rebalancing problem with space and resource restrictions (MTALRBP-SR). The aim is to find lines’ rebalance with the trade-off between efficiency, rebalancing cost and smoothing after reconfiguration. IICA utilises a new initialisation heuristic procedure based on classic heuristic rules to generate feasible initial solutions. A novel heuristic assimilation method is developed to vigorously conduct local search. In addition, a group-based decoding heuristic procedure is developed to fulfil the final task reassignment with the additional restrictions. To investigate the performance of the proposed algorithm, it is first tested on MTALRBP of benchmark problems and compared with some existing algorithms such as genetic algorithm, variable neighbourhood search algorithm, discrete artificial bee colony algorithm, and two iterated greedy algorithms. Next, the efficiency of the proposed IICA for solving MTALRBP-SR is revealed by comparison with a non-dominated sorting genetic algorithm (NSGA-II) and two versions of original ICA. Computational results and comparisons show the efficiency and effectiveness of IICA. Furthermore, a real-world case study is conducted to validate the proposed algorithm.     

Exact algorithms for the feedback length minimisation problem

Planning the sequence of interrelated activities of production and manufacturing systems has become a challenging issue due to the existence of cyclic information flows. This study develops efficient exact algorithms for finding an activity sequence with minimum total feedback length in a design structure matrix. First, we present two new properties of the problem. Second, based on the properties, we develop an efficient Parallel Branch-and-Prune algorithm (PBP). Finally, the proposed PBP is further improved by adopting hash functions representing activity sequences, which is referred as hash function-based PBP. Experimental results indicate that the proposed hash function-based PBP can find optimal solutions for problems up to 25 interrelated activities within 1 h, and outperforms existing methods.     

Open shop scheduling problem to minimize total weighted completion time

A given number of jobs in an open shop scheduling environment must each be processed for given amounts of time on each of a given set of machines in an arbitrary sequence. This study aims to achieve a schedule that minimizes total weighted completion time. Owing to the strong NP-hardness of the problem, the weighted shortest processing time block (WSPTB) heuristic is presented to obtain approximate solutions for large-scale problems. Performance analysis proves the asymptotic optimality of the WSPTB heuristic in the sense of probability limits. The largest weight block rule is provided to seek optimal schedules in polynomial time for a special case. A hybrid discrete differential evolution algorithm is designed to obtain high-quality solutions for moderate-scale problems. Simulation experiments demonstrate the effectiveness of the proposed algorithms.     

Sequencing minimum product sets on mixed-model U-lines to minimise work overload

In a mixed-model assembly line (MMAL), varying models of the same basic product are produced in a facultative sequence. This gives rise to the short-term model sequencing problem, which has to decide on the production sequence of a given number of model copies so that work overload is minimised. Recently, many MMALs have been arranged in ‘U-lines’, where one operator supervises both the entrance and the exit. This paper addresses the model sequencing problem on a paced mixed-model U-line in a cyclic production environment. Some useful properties of the problem are characterised, and the problem is formulated to minimise the steady-state work overload. A branch-and-bound algorithm is proposed to solve small-sized problems, and a heuristic is proposed for practical-sized problems. Numerical experiments on 540 randomly generated instances show that the proposed heuristic can find near-optimal solutions efficiently.     

An integrated formulation for hierarchical cast design problems in the steel making industry

Production design is a key decision problem of steel making industry but due to its complexity, solution properties are not well understood. The design problem can be viewed as a multi-stage problem of bin packing, matching and sequencing sub-problems. Traditionally a sequential approach which treats each sub-problem separately has been applied to the simple case where mould width change is not allowed. However, for more general cases where casting with width change and different width is allowed, the sequential approach fails to generate good solutions. In this paper, we propose a mathematical programming formulation which can solve the design problem in an integrative way. By introducing multi-layer network representation of the cast design problem, it is now possible to generate an integrated formulation for the proposed problem. Based on the formulation, we derive a heuristic algorithm. The algorithm is adopted and tested at a large international integrated steel mill. The computational tests with real data-sets show that the proposed algorithm is quite effective and practical.     

A block transportation scheduling system considering a minimisation of travel distance without loading of and interference between multiple transporters

Material transportation scheduling problems concerning scheduling optimisation have been extensively investigated by researchers in such fields as industrial engineering and management science. Various algorithms have been proposed to solve such problems. However, the majority of these algorithms cannot be applied to a block transportation problem when a shipyard that uses a transporter, a large vehicle employed for moving weight, is considered. In this study, a hybrid optimisation algorithm is proposed for solving a block transportation problem when multiple transporters are used. With regards to the transporters, a minimisation of the travel distance without loading of and interference between the transporters is considered. A block transportation scheduling system is then developed based on the proposed algorithm. The developed system is applied to an actual block transportation scheduling problem of a shipyard. From the attained results, we demonstrate that the proposed algorithm has the ability to effectively solve the block transportation scheduling problems of a shipyard.     

Scheduling TV commercials using genetic algorithms

In this paper, the problem of scheduling commercial messages during the peak of viewing time of a TV channel is formulated as a combinatorial auction-based mathematical programming model. Through this model, a profitable and efficient mechanism for allocating the advertising time to advertisers is developed by which the revenue of TV channels is maximised while the effectiveness of advertising is increased. We developed a steady-state genetic algorithm to find an optimal or a near optimal solution for the proposed problem. A computational experiment was conducted for evaluating the efficiency of the proposed algorithm. A set of test problems with different sizes were generated, using the pseudo-random generation mechanism, and solved by the proposed genetic algorithm. The optimal solutions of the linear programming relaxation of these test problems were also obtained and were used for evaluating the quality of solutions obtained by the developed algorithm. The results of this computational experiment revealed the robustness of the solutions and acceptably low computational time for obtaining these solutions. The computational results also demonstrated that the proposed genetic algorithm had an appropriate ability to preserve population diversity during the search and was capable of obtaining high-quality solutions for the proposed problem.     

An artificial bee colony algorithm for the economic lot scheduling problem

In this study, we present an artificial bee colony (ABC) algorithm for the economic lot scheduling problem modelled through the extended basic period (EBP) approach. We allow both power-of-two (PoT) and non-power-of-two multipliers in the solution representation. We develop mutation strategies to generate neighbouring food sources for the ABC algorithm and these strategies are also used to develop two different variable neighbourhood search algorithms to further enhance the solution quality. Our algorithm maintains both feasible and infeasible solutions in the population through the use of some sophisticated constraint handling methods. Experimental results show that the proposed algorithm succeeds to find the all the best-known EBP solutions for the high utilisation 10-item benchmark problems and improves the best known solutions for two of the six low utilisation 10-item benchmark problems. In addition, we develop a new problem instance with 50 items and run it at different utilisation levels ranging from 50 to 99% to see the effectiveness of the proposed algorithm on large instances. We show that the proposed ABC algorithm with mixed solution representation outperforms the ABC that is restricted only to PoT multipliers at almost all utilisation levels of the large instance.     

A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

Modelling and a tabu search solution for the slab reallocation problem in the steel industry

This paper considers a slab reallocation problem arising from operations planning in the steel industry. The problem involves reallocating steel slabs to customer orders to improve the utilisation of slabs and the level of customer satisfaction. It can be viewed as an extension of a multiple knapsack problem. We firstly formulate the problem as an integer nonlinear programming (INLP) model. With variable replacement, the INLP model is then transformed into a mixed integer linear programming (MILP) model, which can be solved to optimality by MILP optimisers for very small instances. To obtain satisfactory solutions efficiently for practical-sized instances, a heuristic algorithm based on tabu search (TS) is proposed. The algorithm employs multiple neighbourhoods including swap, insertion and ejection chain in local search, and adopts solution space decomposition to speed up computation. In the ejection chain neighbourhood, a new and more effective search method is also proposed to take advantage of the structural properties of the problem. Computational experiments on real data from an advanced iron and steel company in China show that the algorithm generates very good results within a short time. Based on the model and solution approach, a decision support system has been developed and implemented in the company.     

Many-objective harmony search for integrated order planning in steelmaking-continuous casting-hot rolling production of multi-plants

This paper investigates a challenging problem of integrated order planning (IOP) in steelmaking-continuous casting-hot rolling production of multiple plants with consideration of four conflicting objectives. The objective functions refer to the earliness/tardiness ratio, the non-hot charge ratio and the imbalance ratio of production capacity utilisation corresponding to SCC plants and HR Plants. The IOP guided by the integration strategy, which includes the vertical integration of production stages and the horizontal integration of steel plants, is regarded as a large-scale many-objective optimisation problem. To deal with the difficulty of large-scale decision variables, we introduce a new concept named ‘order-set’ for modelling. In addition, a novel knee point-driven many-objective global-best harmony search (KGHS) algorithm, mainly integrating a KGHS process and a new knee point-driven Pareto optimisation, is developed to tackle this many-objective problem. The proposed model and algorithm were tested with benchmarks and real production data. Experiments demonstrate that the proposed approach generates effective solutions superior to those generated by the other popular many-objective optimisation methods.     

Design of high-performing hybrid meta-heuristics for unrelated parallel machine scheduling with machine eligibility and precedence constraints

This study involves an unrelated parallel machine scheduling problem in which sequence-dependent set-up times, different release dates, machine eligibility and precedence constraints are considered to minimize total late works. A new mixed-integer programming model is presented and two efficient hybrid meta-heuristics, genetic algorithm and ant colony optimization, combined with the acceptance strategy of the simulated annealing algorithm (Metropolis acceptance rule), are proposed to solve this problem. Manifestly, the precedence constraints greatly increase the complexity of the scheduling problem to generate feasible solutions, especially in a parallel machine environment. In this research, a new corrective algorithm is proposed to obtain the feasibility in all stages of the algorithms. The performance of the proposed algorithms is evaluated in numerical examples. The results indicate that the suggested hybrid ant colony optimization statistically outperformed the proposed hybrid genetic algorithm in solving large-size test problems.     

A nested column generation algorithm to the meta slab allocation problem in the steel making industry

This paper addresses one of the key operational decision problems in the steel industry which is related to the allocation of orders to stock materials in the surplus inventory. The meta slab allocation problem can be stated as the ‘multi-stage multiple knapsack problem’ where the problem is to design slabs using orders with similar properties (the first stage) and allocating these designed slabs into the existing meta slabs in the inventory yard (the second stage). The objective of the problem is to maximise the allocated order weights in slabs and meta slabs. For the given problem, we propose a column generation algorithm, where a column in the master problem represents meta slabs and the sub problem is to design ‘bins’, here slabs with the given orders. The sub problem itself also becomes a multiple knapsack problem and we proposed a practical set-partitioning heuristic. The proposed algorithm was tested with daily operation data given from an integrated steel company in the Asia Pacific. The computational results showed that the proposed heuristic solved the real instances pretty well. The proposed algorithm was successfully deployed to the integrated steel mill.     

Ant system for reliability optimization of a series system with multiple-choice and budget constraints

Many researchers have shown that insect colonies behavior can be seen as a natural model of collective problem solving. The analogy between the way ants look for food and combinatorial optimization problems has given rise to a new computational paradigm, which is called ant system. This paper presents an application of ant system in a reliability optimization problem for a series system with multiple-choice constraints incorporated at each subsystem, to maximize the system reliability subject to the system budget. The problem is formulated as a nonlinear binary integer programming problem and characterized as an NP-hard problem. This problem is solved by developing and demonstrating a problem-specific ant system algorithm. In this algorithm, solutions of the reliability optimization problem are repeatedly constructed by considering the trace factor and the desirability factor. A local search is used to improve the quality of the solutions obtained by each ant. A penalty factor is introduced to deal with the budget constraint. Simulations have shown that the proposed ant system is efficient with respect to the quality of solutions and the computing time.