Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution

This paper studies the single-hoist cyclic scheduling problem in electroplating systems with two extended features. One extension is that the products must visit some processing tanks more than once (multi-function tanks). Another is that more than one identical tank is used at some stages. These extensions are common in practical electroplating lines and can increase the lines' processing capacity. However, they make the hoist scheduling problem more complicated and little research has been done to optimize the hoist moves in such extended practical systems. In this paper, we develop a comprehensive mixed integer linear programming model to find optimal solutions to the single-hoist cyclic scheduling problem for electroplating lines with these extensions. Examples are given to demonstrate the effectiveness of the model in different types of problems.     

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.     

Working time constraints in operational fixed job scheduling

In this study we consider the operational fixed job scheduling problem under working time limitations. The problem has several practical implications in both production and service operations; however the relevant research is scarce. We analyse pre-emptive and non pre-emptive versions of the problem and its special cases. We provide polynomial-time algorithms for some special cases. We show that the non pre-emptive jobs problem is strongly NP-hard, and propose a branch-and-bound algorithm that employs efficient bounding procedures and dominance properties. We conduct a numerical experiment to observe the effects of parameters on the quality of the solution. The results of our computational tests for the branch-and-bound algorithm reveal that our algorithm can solve the instances with up to 100 jobs in reasonable times. To the best of our knowledge our branch-and-bound algorithm is the first optimisation attempt to solve the problem.     

A fixed job scheduling problem with machine-dependent job weights

This study considers the identical parallel machines operational fixed job scheduling problem with machine-dependent job weights. A job is either processed in a fixed interval or is not processed at all. Our aim is to maximise the total weight of the processed jobs. We show that the problem with machine eligibility constraints resides as a special case of this problem. We identify some special polynomially solvable cases and propose a branch-and-bound (BB) algorithm that employs efficient bounding schemes and dominance conditions. Computational experience on large-sized problem examples reveals the satisfactory performance of the BB algorithm.     

Intelligent scheduling of discrete automated production line via deep reinforcement learning

The reinforcement learning (RL) is being used for scheduling to improve the adaptability and flexibility of an automated production line. However, the existing methods only consider processing time certain and known and ignore production line layouts and transfer unit, such as robots. This paper introduces deep RL to schedule an automated production line, avoiding manually extracted features and overcoming the lack of structured data sets. Firstly, we present a state modelling method in discrete automated production lines, which is suitable for linear, parallel and re-entrant production lines of multiple processing units. Secondly, we propose an intelligent scheduling algorithm based on deep RL for scheduling automated production lines. The algorithm establishes a discrete-event simulation environment for deep RL, solving the confliction of advancing transferring time and the most recent event time. Finally, we apply the intelligent scheduling algorithm into scheduling linear, parallel and re-entrant automated production lines. The experiment shows that our scheduling strategy can achieve competitive performance to the heuristic scheduling methods and maintains stable convergence and robustness under processing time randomness.     

Solution algorithms for single-machine group scheduling with ready times and deteriorating jobs

This article considers the single-machine group scheduling problem with deterioration effect and ready times. The objective of this problem is to determine the sequence of groups and the sequence of jobs to minimize the makespan. To solve the problem, an algorithm based on enumeration, an heuristic algorithm and a branch-and-bound algorithm are developed and exhaustively tested. The computational results show that the performance of the heuristic algorithm is fairly accurate in obtaining near-optimal solutions and the branch-and-bound algorithm is very effective in obtaining optimal solutions.     

Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect

This paper deals with a single-machine scheduling problem with a time-dependent learning effect. The goal is to determine the job sequence that minimise the number of tardy jobs. Two dominance properties, two heuristic algorithms and a lower bound to speed up the search process of the branch-and-bound algorithm are proposed. Computational experiments show that the branch-and-bound algorithm can solve instances up to 18 jobs in a reasonable amount of time, and the proposed heuristic algorithm MFLA performs effectively and efficiently     

An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance

In this paper, we investigate a single-machine scheduling problem with periodic maintenance, which is motivated by various industrial applications (e.g. tool changes). The pursued objective is to minimise the number of tardy jobs, because it is one of the important criteria for the manufacturers to avoid the loss of customers. The strong NP-hardness of the problem is shown. To improve the state-of-the-art exact algorithm, we devise a new branch-and-bound algorithm based on an efficient lower bounding procedure and several new dominance properties. Numerical experiments are conducted to demonstrate the efficiency of our exact algorithm.     

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.     

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.     

Bi-objective scheduling on uniform parallel machines considering electricity cost

This article investigates a bi-objective scheduling problem on uniform parallel machines considering electricity cost under time-dependent or time-of-use electricity tariffs, where electricity price changes with the hours within a day. The aim is to minimize simultaneously the total electricity cost and the number of machines actually used. A bi-objective mixed-integer linear programming model is first formulated for the problem. An insertion algorithm is then proposed for the single-objective scheduling problem of minimizing the total electricity cost for a given number of machines. To obtain the whole Pareto front of the problem, an iterative search framework is developed based on the proposed insertion algorithm. Computational results on real-life and randomly generated instances demonstrate that the proposed approach is quite efficient and can find high-quality Pareto fronts for large-size problems with up to 5000 jobs.     

双机无等待流水作业调度算法研究

考虑双机无等待流水作业调度问题,此问题中每台机器都受一个非可用时间的约束,工件都有不同的释放时间。机器的非可用性时间间隔是部分重叠并且已知。目标使Makespan(最大流程时间)最小。通过不同的方式计算上限和下限,完善分支定界法。计算机实验结果显示了所述方法的有效性。     

No-wait scheduling of a two-machine flow-shop to minimise the makespan under non-availability constraints and different release dates

In this paper, we consider the two-machine no-wait flow-shop scheduling problem, when every machine is subject to one non-availability constraint and jobs have different release dates. The non-availability intervals of the machines overlap and they are known in advance. We aim to find a non-resumable schedule that minimises the makespan. We propose several lower bounds and upper bounds. These bounding procedures are used in a branch-and-bound algorithm. Computational experiments are carried out on a large set of instances and the obtained results show the effectiveness of our method.     

Multi-population genetic algorithm to solve the synchronized and integrated two-level lot sizing and scheduling problem

This paper introduces an evolutionary algorithm as a procedure to solve the Synchronized and Integrated Two-Level Lot Sizing and Scheduling Problem (SITLSP). This problem can be found in some industrial settings, mainly soft drink companies, where the production process involves two interdependent levels with decisions concerning raw material storage and soft drink bottling. The challenge is to simultaneously determine the lot-sizing and scheduling of raw materials in tanks and soft drinks in bottling lines, where setup costs and times depend on the previous items stored and bottled. A multi-population genetic algorithm approach with a novel representation of solutions for individuals and a hierarchical ternary tree structure for populations is proposed. Computational tests include comparisons with an exact approach for small-to-moderate-sized instances and with real-world production plans provided by a manufacturer.     

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

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

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.     

Scheduling continuous aluminium casting lines

This study considers the problem of scheduling casting lines of an aluminium casting and processing plant. In aluminium processing plants, continuous casting lines are the bottleneck resources, i.e. factory throughput is limited by the amount of aluminium that can be cast. The throughput of a casting line might be increased by minimizing total setup time between jobs. The objective is to minimize setup time on production lines for a given time period while balancing workload between production lines to accommodate potential new orders. A mathematical formulation for scheduling jobs to minimize the total setup time while achieving workload balance between the production lines is presented. Since the casting scheduling problem is an NP-hard problem, even with only one casting line, a four-step algorithm to find good solutions in a reasonable amount of time is proposed. In this process, a set of asymmetric travelling salesman problems is followed by a pairwise exchange heuristic. The proposed procedure is applied to a case study using real casting data.     

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.     

A two-stage three-machine assembly scheduling problem with a position-based learning effect

The two-stage assembly scheduling problem has attracted increasing research attention. In many such problems, job processing times are commonly assumed to be fixed. However, this assumption does not hold in many real production situations. In fact, processing times usually decrease steadily when the same task is performed repeatedly. Therefore, in this study, we investigated a two-stage assembly position-based learning scheduling problem with two machines in the first stage and an assembly machine in the second stage. The objective was to complete all jobs as soon as possible (or to minimise the makespan, implying that the system can perform better and efficient task planning with limited resources). Because this problem is NP-hard, we derived some dominance relations and a lower bound for the branch-and-bound method for finding the optimal solution. We also propose three heuristics, three versions of the simulated annealing (SA) algorithm, and three versions of cloud theory-based simulated annealing algorithm for determining near-optimal solutions. Finally, we report the performance levels of the proposed algorithms.     

A hybrid nested partitions algorithm for scheduling flexible resource in flow shop problem

Production scheduling with flexible resources is critical and challenging in many modern manufacturing firms. This paper applies the nested partitions (NP) framework to solve the flexible resource flow shop scheduling (FRFS) problem using an efficient hybrid NP algorithm. By considering the domain knowledge, the ordinal optimisation principle and the NEH heuristics are integrated into the partitioning scheme to search the feasible region. An efficient resource-allocation procedure is built into the sampling scheme for the FRFS problem. A large number of benchmark examples with flexible resources are tested. The test results show that the hybrid NP algorithm is more efficient than either generic NP or heuristics alone. The algorithm developed in this study is capable of selecting the most promising region for a manufacturing system with a high degree of accuracy. The algorithm is efficient and scalable for large-scale problems.