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.     

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     

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.     

A branch-and-bound algorithm for the single-row equidistant facility layout problem

In this paper, we deal with the single-row equidistant facility layout problem (SREFLP), which asks to find a one-to-one assignment of n facilities to n locations equally spaced along a straight line so as to minimize the sum of the products of the flows and distances between facilities. We develop a branch-and-bound algorithm for solving this problem. The lower bound is computed first by performing transformation of the flow matrix and then applying the well-known Gilmore–Lawler bounding technique. The algorithm also incorporates a dominance test which allows to drastically reduce redundancy in the search process. The test is based on the use of a tabu search procedure designed to solve the SREFLP. We provide computational results for problem instances of size up to 35 facilities. For a number of instances, the optimal value of the objective function appeared to be smaller than the best value reported in the literature.     

Experiments with hybrid Bernstein global optimization algorithm for the OPF problem in power systems

This article presents an algorithm based on the Bernstein form of polynomials for solving the optimal power flow (OPF) problem in electrical power networks. The proposed algorithm combines local and global optimization methods and is therefore referred to as a ‘hybrid’ Bernstein algorithm in the context of this work. The proposed algorithm is a branch-and-bound procedure wherein a local search method is used to obtain a good upper bound on the global minimum at each branching node. Subsequently, the Bernstein form of polynomials is used to obtain a lower bound on the global minimum. The performance of the proposed algorithm is compared with the previously reported Bernstein algorithm to demonstrate its efficacy in terms of the chosen performance metrics. Furthermore, the proposed algorithm is tested on the OPF problem for several benchmark IEEE power system examples and its performance is compared with generic global optimization solvers such as BARON and COUENNE. The test results demonstrate that the hybrid Bernstein global optimization algorithm delivers satisfactory performance in terms of solution optimality.     

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.     

DESIGNING CELLULAR MANUFACTURING SYSTEMS: BRANCH-AND-BOUND AND A* APPROACHES

In this paper, heuristic and optimal algorithms for solving the group technology problem are presented. The heuristic algorithm is based on a branch-and-bound concept. A quadratic programming model for the machine grouping problem is formulated. The A* algorithm is developed for optimal solving of the machine grouping problem. The performance of the heuristic branch-and-bound method and the A* algorithm is compared with several existing heuristics.     

Flow shop-sequencing problem with synchronous transfers and makespan minimization

This study considers a permutation flow shop-sequencing problem with synchronous transfers between stations. The objective is to minimize the makespan. It is shown that the problem is strongly NP-hard. A branch-and-bound algorithm together with several lower and upper bounding procedures are developed. The algorithm returns optimal solutions to moderate-sized problem instances in reasonable solution times.     

Two-machine flow-shop scheduling to minimize total late work: revisited

This article revisits the scheduling problem in a two-machine flow-shop system with the total late work criterion, which penalizes parts of jobs executed after their due dates. Firstly, it is shown that a lower bound presented previously in the literature, in the context of a branch-and-bound algorithm proposed for the same problem, is invalid. Then a novel proposal of the branch-and-bound method is given equipped with a new lower-bound technique, as well as an upper-bound and dominance rules. Numerical experiments show that the newly proposed lower-bound technique works well in cutting unpromising branches.     

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.     

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 two-phase computational scheme for solving bang-bang control problems

This paper focuses on numerical methods for solving time-optimal control problems using discrete-valued controls. A numerical Two-Phase Scheme, which combines admissible optimal control problem formulation with enhanced branch-and-bound algorithms, is introduced to efficiently solve bang-bang control problems in the field of engineering. In Phase I, the discrete restrictions are relaxed, and the resulting continuous problem is solved by an existing optimal control solver. The information on switching times obtained in Phase I is then used in Phase II wherein the discrete-valued control problem is solved using the proposed algorithm. Two numerical examples, including a third-order system and the F-8 fighter aircraft control problem, are presented to demonstrate the use of this proposed scheme. Comparing to STC and CPET methods proposed in the literature, the proposed scheme provides a novel method to find a different switching structure with a better minimum time for the F-8 fighter jet control problem.     

Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities

This article considers a single machine scheduling problem with batch setups, positional deterioration effects, and multiple optional rate-modifying activities to minimize the total completion time. This problem is formulated as an integer quadratic programming problem. In view of the complexity of optimally solving this problem, a two-phase heuristic algorithm is proposed where an optimal but non-integer solution is obtained in the first phase by solving a continuous relaxed version of the problem. This solution serves as a lower bound for the optimal value of the total completion time. The second phase of the algorithm generates an integer solution using a simple rounding scheme that is optimum or very close to optimum for this problem. Empirical evaluation and comparison with an existing heuristic algorithm show that the proposed heuristic algorithm is substantially more effective in solving large-size problem instances.     

考虑任务拆分特性与簇准备时间的并行机调度

在印制电路板钻孔任务调度等工程实际中,普遍存在一类具有任务拆分特性与簇准备时间的并行机调度问题,尚缺乏高效的优化模型和方法。针对该问题,首先建立以总拖期最小为目标的数学模型,以约束的形式将两个现有优势定理嵌入其中。为了高效求解实际规模问题,进一步提出嵌入优势定理的模拟退火算法。最后,基于随机生成的算例构造计算实验,以验证所建模型和算法的有效性。实验结果表明,嵌入优势定理的数学模型在问题求解规模和计算效率方面均优于现有数学模型,嵌入优势定理的模拟退火算法同样优于现有模拟退火算法。     

Computing the lowest equilibrium pose of a cable-suspended rigid body

We solve the problem of finding the lowest stable-equilibrium pose of a rigid body subjected to gravity and suspended in space by an arbitrary number of cables. Besides representing a contribution to fundamental rigid-body mechanics, this solution finds application in two areas of robotics research: underconstrained cable-driven parallel robots and cooperative towing. The proposed approach consists in globally minimizing the rigid-body potential energy. This is done by applying a branch-and-bound algorithm over the group of rotations, which is partitioned into boxes in the space of Euler-Rodrigues parameters. The lower bound on the objective is obtained through a semidefinite relaxation of the optimization problem, whereas the upper bound is obtained by solving the same problem for a fixed orientation. The resulting algorithm is applied to several examples drawn from the literature. The reported Matlab implementation converges to the lowest stable equilibrium pose generally in a few seconds for cable-robot applications. Interestingly, the proposed method is only mildly sensitive to the number of suspending cables, which is shown by solving an example with 1000 cables in two hours.     

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

考虑双机无等待流水作业调度问题,此问题中每台机器都受一个非可用时间的约束,工件都有不同的释放时间。机器的非可用性时间间隔是部分重叠并且已知。目标使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.     

Multiprocessor task scheduling problem using hybrid discrete particle swarm optimization

Task Scheduling is a complex combinatorial optimization problem and known to be an NP hard. It is an important challenging issue in multiprocessor computing systems. Discrete Particle Swarm Optimization (DPSO) is a newly developed swarm intelligence technique for solving discrete optimization problems efficiently. In DPSO, each particle should limit its communication with the previous best solution and the best solutions of its neighbors. This learning restriction may reduce the diversity of the algorithm and also the possibility of occurring premature convergence problem. In order to address these issues, the proposed work presents a hybrid version of DPSO which is a combination of DPSO and Cyber Swarm Algorithm (CSA). The efficiency of the proposed algorithm is evaluated based on a set of benchmark instances and the performance criteria such as makespan, mean flow time and reliability cost.     

Single machine scheduling with preventive maintenances

We consider the single machine total flow time problem in which the jobs are non-resumable and the machine is subject to preventive maintenance activities of known starting times and durations. We propose a branch-and-bound algorithm that employs powerful optimality properties and bounding procedures. Our extensive computational studies show that our algorithm can solve large-sized problem instances with up to 80 jobs in reasonable times. We also study a two-alternative maintenance planning problem with minor and major maintenances. We give a polynomial-time algorithm to find the optimal maintenance times when the job sequence is fixed.     

带非凸二次约束的二次规划问题的全局优化方法

利用二次函数的线形下界函数对带有非凸二次约束的二次规划(QP)提出一种新的求其全局最优解的分支定界算法.为改进算法的收敛性,根据问题的最优性和可行性提出一新的区域剪枝准则以排除(QP)的可行域中不存在全局解的部分.数值算例表明该准则能有效地加速算法的收敛性.