A single machine carryover sequence-dependent group scheduling in PCB manufacturing

This paper considers the problem of minimizing the makespan on a single machine with carryover sequence-dependent setup times. A similar problem with multi-machine flow shop usually arises in the assembly of printed circuit boards (PCBs). This research investigates the possibility of processing all components of PCBs using just one machine. By doing so the operational costs of having multi-machines can be reduced, and as a result, finding an optimal solution might be more plausible. The objective is to minimize the maximum completion time of all board groups, commonly known as makespan. The operational constraints are such that all board types within a board group must be completely kitted, as it is traditionally performed by kitting staff, before that board group begins its assembly operation. We introduce the external setup (kitting) time and require that it be performed solely by the machine operator during the run time of the current board group, and thereby completely eliminating the need for kitting staff. The carryover sequence-dependent setup time, namely the internal (machine) setup time, is realized when a new board group is ready for assembly operation and is dependent on all of the previously scheduled board groups and their sequences. To the best of our knowledge, this is the first time the external and internal setup times are integrated in PCB group scheduling research. We develop a branch-and-bound algorithm and a lower-bounding structure. The lower bound consists of two approaches, which enable the algorithm to simultaneously reduce performing unnecessary exploration. In order to test the efficiency of the algorithm, several problem instances with different board groups have been used. The algorithm developed requires a significantly large computation time to optimally solve very large problems. Thus to speak for the efficiency in terms of solving comparable large industry-size problems, we evaluate the deviation of the algorithm from the lower bound which turns out to be very small, with an average of only 6%, in all of the problem instances considered.     

Scheduling two-machine no-wait open shops to minimize makespan

This paper examines the problem of scheduling two-machine no-wait open shops to minimize makespan. The problem is known to be strongly NP-hard. An exact algorithm, based on a branch-and-bound scheme, is developed to optimally solve medium-size problems. A number of dominance rules are proposed to improve the search efficiency of the branch-and-bound algorithm. An efficient two-phase heuristic algorithm is presented for solving large-size problems. Computational results show that the branch-and-bound algorithm can solve problems with up to 100 jobs within a reasonable amount of time. For large-size problems, the solution obtained by the heuristic algorithm has an average percentage deviation of 0.24% from a lower bound value.     

A hybrid evolutionary algorithm for the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) is an NP-hard optimization problem. RCPSP is one of the most important and challenging problems in the project management field. In the past few years, many researches have been proposed for solving the RCPSP. The objective of this problem is to schedule the activities under limited resources so that the project makespan is minimized. This paper proposes a new algorithm for solving RCPSP that combines the concepts of negative selection mechanism of the biologic immune system, simulated annealing algorithm (SA), tabu search algorithm (TS) and genetic algorithm (GA) together. The performance of the proposed algorithm is evaluated and compared to current state-of-the-art metaheuristic algorithms. In this study, the benchmark data sets used in testing the performance of the proposed algorithm are obtained from the project scheduling problem library. The performance is measured in terms of the average percentage deviation from the critical path lower bound. The experimental results show that the proposed algorithm outperforms the state-of-the-art metaheuristic algorithms on all standard benchmark data sets.     

Non-permutation flowshop scheduling with dual resources

Typically, in order to process jobs in a flowshop both machines and labor are required. However, in traditional scheduling problems, labor is assumed to be plentiful and only machine is considered to be a constraint. This assumption could be due to the lower cost of labor compared to machines or the complexity of dual-resource constrained problems. In this paper a mathematical model is developed to minimize the work-in-process inventory while maximizing the service level in a flowshop with dual resources. The model focuses on optimizing a non-permutation flowshop. There are different skill levels considered for labor and the setup times on machines are sequence-dependent. Jobs are allowed to skip one or more stages in the flowshop. Job release and machine availability times are considered to be dynamic. The problem is solved in two layers. The outer layer is a search algorithm to find the schedule of jobs on the machine (traditional flowshop scheduling problem) and the inner layer is a three-step heuristic to find a schedule of jobs on labor in accordance to the machine schedule. Three different search algorithms are developed to solve the proposed NP-hard problem. First algorithm can solve a permutation flowshop while the other two are developed to solve a non-permutation flowshop. The comparison between the optimal solution and the search algorithms in small examples shows a good performance of the algorithms with an average deviation of only 2.00%. An experimental design analyzes the effectiveness and efficiency of the algorithms statistically. The results show that non-permutation algorithms perform better than the permutation algorithm, although the former are less efficient. The effectiveness and efficiency in all three algorithms have an inverse relation. To the best of our knowledge, this research is the first of its kind to provide a comprehensive mathematical model for dual resource flowshop scheduling problem.     

Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times

We consider a two-machine re-entrant flowshop scheduling problem in which all jobs must be processed twice on each machine and there are sequence-dependent setup times on the second machine. For the problem with the objective of minimizing total tardiness, we develop dominance properties and a lower bound by extending those for a two-machine re-entrant flowshop problem (without sequence-dependent setup times) as well as heuristic algorithms, and present a branch and bound algorithm in which these dominance properties, lower bound, and heuristics are used. For evaluation of the performance of the branch and bound algorithm and heuristics, computational experiments are performed on randomly generated instances, and results are reported.     

Artificial chromosomes with genetic algorithm 2 (ACGA2) for single machine scheduling problems with sequence-dependent setup times

Artificial chromosomes with genetic algorithm (ACGA) is one of the latest versions of the estimation of distribution algorithms (EDAs). This algorithm has already been applied successfully to solve different kinds of scheduling problems. However, due to the fact that its probabilistic model does not consider variable interactions, ACGA may not perform well in some scheduling problems, particularly if sequence-dependent setup times are considered. This is due to the fact that the previous job will influence the processing time of the next job. Simply capturing ordinal information from the parental distribution is not sufficient for a probabilistic model. As a result, this paper proposes a bi-variate probabilistic model to add into the ACGA. This new algorithm is called the ACGA2 and is used to solve single machine scheduling problems with sequence-dependent setup times in a common due-date environment. A theoretical analysis is given in this paper. Some heuristics and local search algorithm variable neighborhood search (VNS) are also employed in the ACGA2. The results indicate that the average error ratio of this ACGA2 is half the error ratio of the ACGA. In addition, when ACGA2 is applied in combination with other heuristic methods and VNS, the hybrid algorithm achieves optimal solution quality in comparison with other algorithms in the literature. Thus, the proposed algorithms are effective for solving the scheduling problems.     

Scheduling unrelated parallel machines with sequence-dependent setups

A methodology for minimizing the weighted tardiness of jobs in unrelated parallel machining scheduling with sequence-dependent setups is presented in this paper. To comply with industrial situations, the dynamic release of jobs and dynamic availability of machines are assumed. Recognizing the inherent difficulty in solving industrial-size problems efficiently, six different search algorithms based on tabu search are developed to identify the best schedule that gives the minimum weighted tardiness. To enhance both the efficiency and efficacy of the search algorithms, four different initial solution finding mechanisms, based on dispatching rules, are developed. While there is no evidence of identifying solutions of better quality by employing a specific initial solution finding mechanism, the use of a specific search algorithm led to identifying solutions of better quality or that required lower computation time, but not both. Based on the extensive statistical analysis performed, the search algorithm with short-term memory and fixed tabu list size is recommended for solving small size problems, while that with long-term memory and minimum frequency for solving medium and large size problems, combined with fixed tabu list size for the former and variable tabu list size for the latter.     

Graphics processing unit‐accelerated bounding for branch‐and‐bound applied to a permutation problem using data access optimization

Branch‐and‐bound (B&B) algorithms are attractive methods for solving to optimality combinatorial optimization problems using an implicit enumeration of a dynamically built tree‐based search space. Nevertheless, they are time‐consuming when dealing with large problem instances. Therefore, pruning tree nodes (subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space. Pruning requires to perform the bounding operation, which consists of applying a lower bound function to the subproblems generated during the exploration process. Preliminary experiments performed on the Flow‐Shop scheduling problem (FSP) have shown that the bounding operation consumes over 98% of the execution time of the B&B algorithm. In this paper, we investigate the use of graphics processing unit (GPU) computing as a major complementary way to speed up the search. We revisit the design and implementation of the parallel bounding model on GPU accelerators. The proposed approach enables data access optimization. Extensive experiments have been carried out on well‐known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU‐based single core execution using an Intel Core i7‐970 processor without GPU, speedups higher than 100 times faster are achieved for large problem instances. At an equivalent peak performance, GPU‐accelerated B&B is twice faster than its multi‐core counterpart. Copyright © 2013 John Wiley & Sons, Ltd.     

顺序依赖的调整时间和拖期的无缝钢管热轧批量调度算法

无缝钢管热轧生产存在一类特殊的顺序依赖机器调整时间,调整时间依赖于相邻轧制批量间的规格切换,与批量间规格呈线性函数关系.针对具有此类调整时间的热轧批量调度问题,进一步考虑交货期要求,探讨了调整时间与交货期之间的性质特征,并以最小化总机器调整时间和最小化总拖期为目标,基于进化算法框架设计了快速重排序邻域搜索多目标算法(f...     

Greedy randomized adaptive search for dynamic flexible job-shop scheduling

Dynamic flexible job shop scheduling problem is studied under the events such as new order arrivals, changes in due dates, machine breakdowns, order cancellations, and appearance of urgent orders. This paper presents a constructive algorithm which can solve FJSP and DFJSP with machine capacity constraints and sequence-dependent setup times, and employs greedy randomized adaptive search procedure (GRASP). Besides, Order Review Release (ORR) mechanism and order acceptance/rejection decisions are also incorporated into the proposed method in order to adjust capacity execution considering customer due date requirements. The lexicographic method is utilized to assess the objectives: schedule instability, makespan, mean tardiness and mean flow time. A group of experiments is also carried out in order to verify the suitability of the GRASP in solving the flexible job shop scheduling problem. Benchmark problems are formed for different problem scales with dynamic events. The event-driven rescheduling strategy is also compared with periodical rescheduling strategy. Results of the extensive computational experiment presents that proposed approach is very effective and can provide reasonable schedules under event-driven and periodic scheduling scenarios.     

Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach

In scheduling problems, taking the sequence-dependent setup times into account is one of the important issues that have recently been considered by researchers in the production scheduling field. In this paper, we consider flexible job-shop scheduling problem (FJSP) with sequence-dependent setup times to minimize makespan and mean tardiness. The FJSP consists of two sub-problems from which the first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on all machines. To solve this problem, a variable neighborhood search (VNS) algorithm based on integrated approach is proposed. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed the search process. To search the solution space, the internal loop used two main search engines, i.e. shake and local search procedures. In addition, neighborhood structures related to the sequencing problem and the assignment problem were employed to generate neighboring solutions. To evaluate the performance of the proposed algorithm, 20 test problems in different sizes are randomly generated. Consequently, computational results and comparisons validate the quality of the proposed approach.     

基于混合遗传算法的订单生产调度在机车车辆行业中的应用

机车车辆行业作为典型的面向订单的机械制造企业,优化的生产调度方法能提高订单的准时交货,缩短产品的生产周期,提高企业的市场竞争力。订单生产调度问题是典型的NP-hard问题。遗传算法(Genetic Algorithms)为求具有多个约束的复杂问题提供了有效的方法。但是遗传算法的局部搜索能力比较差,在解决订单生产调度问题中存在着明显的不足。本文引入了局部搜索能力很强的禁忌搜索算法,用遗传算法和禁忌搜索算法相结合的混合遗传算法来解决机车车辆行业中面向订单生产调度问题。     

Scheduling image processing tasks in a multilayer system

Multilayer multiprocessor systems are generally employed in real-time applications such as robotics and computer vision. This paper introduces three heuristic algorithms for multiprocessor task scheduling in such systems. In our model, tasks with arbitrary processing times and arbitrary processor requirements are considered. The scheduling aims at minimising completion time of processes in a two-layer system. We employed an effective lower bound (LB) for the problem. Then, we analysed the average performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the LB on a set of randomly generated problems. We have also applied these algorithms for scheduling computer vision tasks running on prototype multilayer architecture. Our computational and empirical results showed that the proposed heuristic algorithms perform well.     

The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

We consider the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup costs and non-zero setup times, with the additional feature that setups may be carried over from one period to the next, and that setups are preserved over idle periods. We provide an exact formulation of this problem as a mixed-integer program.It is well known that the CLSP is NP-hard. Therefore, we have also developed a heuristic for solving large problem instances. This is coupled with a procedure for obtaining a lower bound on the optimal solution. We carry out a computational study to test the accuracy of several different lower bounding linear relaxations and the approximate solution obtained by the heuristic. In our study, the average deviation of the heuristic solution from the corresponding exact solution depends on the size of the problem and ranges from 10 to 16%. The heuristic is more effective when there are many more products than there are planning periods. This is a desirable property from a practical viewpoint since most firms are likely to implement such a procedure on a rolling horizon basis, solving the problem repeatedly for a few periods at a time.     

Dual-Objective Mixed Integer Linear Program and Memetic Algorithm for an Industrial Group Scheduling Problem

Group scheduling problems have attracted much attention owing to their many practical applications. This work proposes a new bi-objective serial-batch group scheduling problem considering the constraints of sequence-dependent setup time, release time, and due time. It is originated from an important industrial process, i.e., wire rod and bar rolling process in steel production systems. Two objective functions, i.e., the number of late jobs and total setup time, are minimized. A mixed integer linear program is established to describe the problem. To obtain its Pareto solutions, we present a memetic algorithm that integrates a population-based nondominated sorting genetic algorithm II and two single-solution-based improvement methods, i.e., an insertion-based local search and an iterated greedy algorithm. The computational results on extensive industrial data with the scale of a one-week schedule show that the proposed algorithm has great performance in solving the concerned problem and outperforms its peers. Its high accuracy and efficiency imply its great potential to be applied to solve industrial-size group scheduling problems.      

An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times

In this paper we consider a multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times by minimizing total weighted tardiness and maximum completion time simultaneously. Whereas these kinds of problems are NP-hard, thus we proposed a multi-population genetic algorithm (MPGA) to search Pareto optimal solution for it. This algorithm comprises two stages. First stage applies combined objective of mentioned objectives and second stage uses previous stage’s results as an initial solution. In the second stage sub-population will be generated by re-arrangement of solutions of first stage. To evaluate performance of the proposed MPGA, it is compared with two distinguished benchmarks, multi-objective genetic algorithm (MOGA) and non-dominated sorting genetic algorithm II (NSGA-II), in three sizes of test problems: small, medium and large. The computational results show that this algorithm performs better than them.     

Tabu search and lower bound for an industrial complex shop scheduling problem

This paper deals with an industrial shop scheduling problem that arises in a metal goods production group. The scheduling problem can be seen as a multi-mode job shop with assembly. Jobs have additional constraints such as release date, due date and sequence-dependent setup times. The aim of the decision-makers is to minimize the maximum lateness. This article introduces a tabu search procedure to solve the whole problem and a valid lower bound used to evaluate the tabu search procedure.     

A time-decomposition method for sequence-dependent setup schedulingunder pressing demand conditions

This paper develops a method for continuous-time scheduling problems in flexible manufacturing systems. The objective is to find the optimal schedule subject to different production constraints: precedence constraints (bills of materials), sequence-dependent setup times, finite machine capacities, and pressing demands. Differential equations along with mixed constraints are used to model production and setup processes in a canonical form of optimal control. The proposed approach to the search for the optimal solution is based on the maximum principle analysis and time-decomposition methodology. To develop fast near-optimal solution algorithms for sizable problems, we replace the general problem with a number of sub-problems so that solving them iteratively provides tight lower and upper estimates of the optimal solution     

Lower bounds on precedence-constrained scheduling for parallel processors

We consider two general precedence-constrained scheduling problems that have wide applicability in the areas of parallel processing, high performance compiling, and digital system synthesis. These problems are intractable so it is important to be able to compute tight bounds on their solutions. A tight lower bound on makespan scheduling can be obtained by replacing precedence constraints with release and due dates, giving a problem that can be efficiently solved. We demonstrate that recursively applying this approach yields a bound that is provably tighter than other known bounds, and experimentally shown to achieve the optimal value at least 90.3% of the time over a synthetic benchmark.We compute the best known lower bound on weighted completion time scheduling by applying the recent discovery of a new algorithm for solving a related scheduling problem. Experiments show that this bound significantly outperforms the linear programming-based bound. We have therefore demonstrated that combinatorial algorithms can be a valuable alternative to linear programming for computing tight bounds on large scheduling problems.     

No-wait two stage hybrid flow shop scheduling with genetic and adaptive imperialist competitive algorithms

This article studies a no-wait two-stage flexible flow shop scheduling problem with setup times aiming to minimize the total completion time. The problem is solved using an adaptive imperialist competitive algorithm (AICA) and genetic algorithm (GA). To test the performance of the proposed AICA and GA, the algorithms are compared with ant colony optimisation, known as an effective algorithm in the literature. The performance of the algorithms are evaluated by solving both small and large-scale problems. Their performance is evaluated in terms of relative percentage deviation. Finally the results of the study are discussed and conclusions and potential areas for further study are highlighted.