A mixed integer linear programming solution for single hoist multi-degree cyclic scheduling with reentrance

This article considers single hoist multi-degree cyclic scheduling problems with reentrance. Time window constraints are also considered. Firstly, a mixed integer programming model is formulated for multi-degree cyclic hoist scheduling without reentrance, referred to as basic lines in this article. Two valid inequalities corresponding to this problem are also presented. Based on the model for basic lines, an extended mixed integer programming model is proposed for more complicated scheduling problems with reentrance. Phillips and Unger's benchmark instance and randomly generated instances are applied to test the model without reentrance, solved using the commercial software CPLEX. The efficiency of the model is analysed based on computational time. Moreover, an example is given to demonstrate the effectiveness of the model with reentrance.     

Multi-degree cyclic hoist scheduling with time window constraints

This paper deals with the multi-degree cyclic single-hoist scheduling problem with time window constraints, in which multiple identical parts enter and leave the system during each cycle. We propose an analytical mathematical model and a branch-and-bound algorithm so as to find a cyclic sequence of hoist moves that maximises the throughput. The branch-and-bound algorithm implicitly enumerates the sequence of hoist moves and requires the solution of a specific set of linear programming problems (LPPs). Computational results on benchmark instances and randomly generated test instances are presented.     

Single-track multi-hoist scheduling problem: a collision-free resolution based on a branch-and-bound approach

An analytical mathematical model and a branch-and-bound algorithm for single-track cyclic multi-hoist scheduling problems are proposed. The objective is to minimize the cycle time for a given number of hoists. The collision-free single-track constraints are first formulated as disjunctive inequalities. It is then shown that this formulation is a very strict and necessary condition. To be a sufficient and necessary one, two additional properties, like collision-checking rules, must hold in optimal solutions. It is proved that a solution violating these two properties due to their relaxation is always dominated by a collision-free one. Therefore, these two properties are relaxed in the branch-and-bound algorithm. The computation of lower bounds in the branch-and-bound algorithm requires the solution of a specific linear programming problem, which can be solved by using a graph-based polynomial algorithm. Computational results with both benchmark and randomly generated test instances are presented.     

Electroplating production scheduling by cyclogram unfolding in dynamic hoist scheduling problem

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

一个改进的单抓钩周期性排序模型及其在自动化学处理线中的应用

计算机控制的抓钩广泛用于自动化学处理线的工件的运送。抓钩的排序直接影响系统的生产率，抓钩排序的目标是对运送进行排序以极大化生产率。当某工序处理时间非常长时，该工序成为瓶颈。为了去除该瓶颈，系统可以为该工序设计多个处理槽，这称为“多重处理槽”问题。本文提出一个改进的混合整数规划模型以求解有“多重处理槽”的单抓钩周期性排序问题的最优解。实例表明所提出的方法是有效的。     

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.     

Cyclic hoist scheduling in large real-life electroplating lines

This paper addresses cyclic scheduling of a single hoist in large real-life electroplating lines, where a part visits some processing tanks more than once and multiple duplicate tanks are used at some production stages having long processing times. We present a formal analysis of the problem and propose an efficient branch-and-bound algorithm. The developed analytical properties allow us to considerably eliminate dominated or infeasible solutions in the branch-and-bound procedure. Computational results on benchmark and real-life instances show that the algorithm is very efficient in scheduling large electroplating lines.     

A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows

A branch and bound algorithm is described for optimal cyclic scheduling in a robotic cell with processing time windows. The objective is to minimise the cycle time by determining the exact processing time on each machine which is limited within a time window. The problem is formulated as a set of prohibited intervals of the cycle time, which is usually applied in the robotic cyclic scheduling problem with fixed processing times. Since both bounds of these prohibited intervals are linear expressions of the processing times, we divide these prohibited intervals into a series of the subsets and transform the problem into enumerating the non-prohibited intervals of cycle time in each subset. This enumeration procedure is completed by an efficient branch and bound algorithm, which could find an optimal solution by enumerating partial non-prohibited intervals. Computational results on the benchmark instances and randomly generated test instances indicate that the algorithm is effective.     

Supply chain optimisation with both production and transportation integration: multiple vehicles for a single perishable product

This paper deals with an extension of the integrated production and transportation scheduling problem (PTSP) by considering multiple vehicles (PTSPm) for optimisation of supply chains. The problem reflects a real concern for industry since production and transportation subproblems are commonly addressed independently or sequentially, which leads to sub-optimal solutions. The problem includes specific capacity constraints, the short lifespan of products and the special case of the single vehicle that has already been studied in the literature. A greedy randomised adaptive search procedure (GRASP) with an evolutionary local search (ELS) is proposed to solve the instances with a single vehicle as a special case. The method has been proven to be more effective than those published and provides shorter computational times with new best solutions for the single vehicle case. A new set of instances with multiple vehicles is introduced to favour equitable future research. Our study extends previous research using an indirect resolution approach and provides an algorithm to solve a wide range of one-machine scheduling problems with the proper coordination of single or multiple vehicles.     

Continuous-time algorithms for scheduling a single machine with sequence-dependent setup times and time window constraints in coordinated chains

In this paper we address the problem of selecting and scheduling several jobs on a single machine with sequence-dependent setup times and strictly enforced time window constraints on the start time of each job. We use short-term production targets to coordinate decentralised local schedulers and to make the objectives of specific areas in line with the chain objectives by maintaining a desired work in process profile in manufacturing environments. The existing literature in this domain is based on discrete-time approaches. We depart from prior approaches by considering continuous time. We introduce a two-step mathematical programming model based on disjunctive constraints to solve small problems to optimality, and propose an insertion-based heuristic to solve large-scale instances. We provide several variations of the insertion heuristic based on different score functions. The primary objective of these approaches is to maximise the total defined score for jobs while satisfying production targets for families of jobs in each shift. Further, our models minimise the maximum completion time of all selected jobs. The effectiveness, efficiency, and robustness of the proposed algorithms are analysed and compared with the existing literature.     

Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines

This paper focuses on simultaneous optimisation of production planning and scheduling problem over a time period for synchronous assembly lines. Differing from traditional top-down approaches, a mixed integer programming model which jointly considers production planning and detailed scheduling constraints is formulated, and a Lagrangian relaxation method is developed for the proposed model, whereby the integrated problem is decomposed into planning, batch sequencing, tardiness and earliness sub-problems. The scheduling sub-problem is modelled as a time-dependent travelling salesman problem, which is solved using a dynasearch algorithm. A proposition of Lagrangian multipliers is established to accelerate the convergence speed of the proposed algorithm. The average direction strategy is employed to solve the Lagrangian dual problem. Test results demonstrate that the proposed model and algorithm are effective and efficient.     

More MILP models for integrated process planning and scheduling

The integration of process planning and scheduling is important for an efficient utilisation of manufacturing resources. In general, there are two types of models for this problem. Although some MILP models have been reported, most existing models belong to the first type and they cannot realise a true integration of process planning and scheduling. Especially, they are completely powerless to deal with the cases where jobs are expressed by network graphs because generating all the process plans from a network graph is difficult and inefficient. The network graph-specific models belong to the other type, and they have seldom been deliberated on. In this research, some novel MILP models for integrated process planning and scheduling in a job shop flexible manufacturing system are developed. By introducing some network graph-oriented constraints to accommodate different operation permutations, the proposed models are able to express and utilise flexibilities contained in network graphs, and hence have the power to solve network graph-based instances. The established models have been tested on typical test bed instances to verify their correctness. Computational results show that this research achieves the anticipant purpose: the proposed models are capable of solving network graph-based instances.     

Auction-based approach for a flexible job-shop scheduling problem with multiple process plans

This study addresses the flexible job-shop scheduling problem with multiple process plans with the objective of minimizing the overall makespan. A nonlinear programming model is formulated to allocate machines and schedule jobs. An auction-based approach is proposed to address the integrated production route selection and resource allocation problem and focus on improving resource utilization and productive efficiency to reduce the makespan. The approach consists of an auction for process plans and an auction for machines. The auctions are evaluated to select a more suitable route for production and allocate resources to a more desirable job. Numerical experiments are conducted by testing new large benchmark instances. A comparison of Lingo and other existing algorithms demonstrates the effectiveness and stability of the proposed auction-based approach. Furthermore, SPSS is used to prove that the proposed method exhibits an absolute advantage, particularly for medium-scale or large-scale instances.     

An improved method for the hot strip mill production scheduling problem

In most research on the hot strip mill production scheduling problem (HSMPSP) arising in the steel industry, it is accepted that a schedule with lower penalty caused by jumps of width, hardness, and gauge will result in lower roller wear, so it is regarded as a better schedule. However, based on the analysis of production processes, it is realised that rolling each coil also cause roller wear. In order to assessing the roller wear associated with production scheduling more precisely, it is necessary to consider it as another factor besides those jumps, especially when complicated constraints are involved. In this paper, an improved method is proposed to quantify the expected wear of the rollers done by those jumps and rolling processes. Then the HSMPSP whose objective is to maximise the total length of all scheduled coils is formulated as a team orienteering problem with time windows and additional production constraints. A heuristic method combining an improved Ant Colony Extended algorithm with local search procedures dedicated to HSMPSP is developed. Finally, computational results on instances generated based on production data from an integrated steel mill in China indicate that the proposed algorithm is a promising solution specific to HSMPSP.     

MIP-based fix-and-optimise algorithms for the parallel machine capacitated lot-sizing and scheduling problem

This paper examines the capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such a problem frequently arises in the semiconductor manufacturing industry by which this paper is motivated. A mixed integer programming (MIP) model is constructed for the problem. Two MIP-based fix-and-optimise algorithms are proposed in which the binary decision variables associated with the assignment of machines are first fixed using the randomised least flexible machine (RLFM) rule and the rest of the decision variables are settled by an MIP solver. Extensive experiments show that the proposed algorithms outperform the state-of-the-art MIP-based fix-and-optimise algorithms in the literature, especially for instances with high machine flexibility and high demand variation.     

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.     

A multi-objective scatter search for the ladle scheduling problem

We consider the ladle scheduling problem, which can be regarded as a vehicle routing problem with semi-soft time windows and adjustment times. The problem concerns allocating ladles to serve molten steel based on a given steelmaking scheduling plan, and determining the modification operations for the empty ladles after the service process. In addition, combining the controllable processing time of molten steel, the other aspect of the problem is to determine the service start times taking into consideration the technological constraints imposed in practice. We present a non-linear mathematical programming model with the conflicting objectives of minimising the occupation ratio of the ladles and maximising the degree of satisfaction with meeting the soft windows. To solve the multi-objective model, we develop a new scatter search (SS) approach by re-designing the common components of SS and incorporating a diversification generator, a combination method and a diversification criterion to conduct a wide exploration of the search space. We analyse and compare the performance of the proposed approach with a multi-objective genetic algorithm and with manual scheduling adopted in practical production using three real-life instances from a well-known iron–steel production plant in China. The computational results demonstrate the effectiveness of the proposed SS approach for solving the ladle scheduling problem.     

Biogeography-based optimisation for flexible manufacturing system scheduling problem

Biogeography-based optimisation (BBO) algorithm is a new evolutionary optimisation algorithm based on geographic distribution of biological organisms. With probabilistic operators, this algorithm is able to share more information from good solutions to poor ones. BBO prevents the good solutions to be demolished during the evolution. This feature leads to find the better solutions in a short time rather than other metaheuristics. This paper provides a mathematical model which integrates machine loading, part routing, sequencing and scheduling decision in flexible manufacturing systems (FMS). Moreover, it tackles the scheduling problem when various constraints are imposed on the system. Since this problem is considered to be NP-hard, BBO algorithm is developed to find the optimum /near optimum solution based on various constraints. In the proposed algorithm, different types of mutation operators are employed to enhance the diversity among the population. The proposed BBO has been applied to the instances with different size and degrees of complexity of problem adopted from the FMS literature. The experimental results demonstrate the effectiveness of the proposed algorithm to find optimum /near optimum solutions within reasonable time. Therefore, BBO algorithm can be used as a useful solution for optimisation in various industrial applications within a reasonable computation time.     

Solving a mixed integer linear program with times setup for the steel-continuous casting planning and scheduling problem

In this paper, we present a novel model that generalise the steelmaking continuous casting planning and scheduling problem. The model includes three stages: converters namely CV, refining stands namely RS and continuous castings namely CC. The obtained problem can be formulated as a mathematical program with typical constraints, namely the times setup constraints. We develop a mixed integer linear program (MILP) to schedule several sequences of charges for more than two continuous castings devices. The aim is: (i) on one hand, to schedule a list of several sequences that are already ordered for each continuous casting with times setup between two successive sequences, (ii) on the other hand, to determine the optimal order of the successive sequences. We use a benchmark and randomly generated instances to test the model and solved by mean of the commercial software solver Cplex v12.5. These problems span a variety of instances varying from small to large sized instances with different intrinsec parameters as the availability date for a converter CV or the variation intervals of the start time for the first charge at the continuous casting CC stage. We analyse the efficiency of the proposed model based on the CPU time and show the time limitations of the model for large instances. Also, we show the robustness of the model when modifying the initial (starting) state.