An MO‐GVNS algorithm for solving a multiobjective hybrid flow shop scheduling problem

This paper addresses the multiobjective hybrid flow shop (MOHFS) scheduling problem. In the MOHFS problem considered here, we have a set of jobs that must be performed in a set of stages. At each stage, we have a set of unrelated parallel machines. Some jobs may skip stages. The evaluation criteria are the minimizations of makespan, the weighted sum of the tardiness, and the weighted sum of the earliness. For solving it, an algorithm based on the multiobjective general variable neighborhood search (MO‐GVNS) metaheuristic, named adapted MO‐GVNS, is proposed. This work also presents and compares the results obtained by the adapted MO‐GVNS with those of four other algorithms: multiobjective reduced variable neighborhood search, nondominated sorting genetic algorithm II (NSGA‐II), and NSGA‐III, and another MO‐GVNS from the literature. The results were evaluated based on the Hypervolume, Epsilon, and Spacing metrics, and statistically validated by the Levene test and confidence interval charts. The results showed the efficiency of the proposed algorithm for solving the MOHFS problem.     

求解差异机器平行批调度的双目标协同蚁群算法

利用用户的偏好信息, 提出一种基于蚁群的双目标协同优化算法(Bi-objective synergy ant colony optimization algorithm based on Pareto domination, PDACO)并用于求解平行批处理机调度问题. 考虑在一组差异容量并带有不同加工功率的平行批处理机器上, 加工带有不同到达时间、尺寸和加工时间的一组工件, 以同时最小化最大完工时间和总能耗. 偏好向量的引入虽然可以提高算法的收敛性, 但会降低解的多样性. 为了弥补这一缺陷, 在本文所提算法中, 利用两个子蚁群分别沿着不同方向, 迭代地进行独立和联合搜索. 最后, 通过大量的仿真实验验证了本文提出算法的有效性.     

A variable neighborhood descent heuristic for the problem of makespan minimisation on unrelated parallel machines with setup times

The NP-hard problem of scheduling jobs on unrelated parallel machines, in the presence of machine-dependent and sequence-dependent setup times, with the objective of minimizing the makespan, is considered. A variable neighborhood descent search algorithm, hybridized with mathematical programming elements, is presented and its performance is evaluated on a large set of benchmark problem instances. The extensive computational experiments show that the proposed algorithm outperforms previously proposed methods in terms of solution quality as well as computation time.     

Metaheuristics and exact methods to solve a multiobjective parallel machines scheduling problem

This paper deals with a multiobjective parallel machines scheduling problem. It consists in scheduling n independent jobs on m identical parallel machines. The job data such as processing times, release dates, due dates and sequence dependent setup times are considered. The goal is to optimize two different objectives: the makespan and the total tardiness. A mixed integer linear program is proposed to model the studied problem. As this problem is NP-hard in the strong sense, a metaheuristic method which is the second version of the non dominated sorting genetic algorithm (NSGA-II) is proposed to solve this problem. Since the parameters setting of a genetic algorithm is difficult, a fuzzy logic controller coupled with the NSGA-II (FLC-NSGA-II) is therefore proposed. The role of the fuzzy logic is to better set the crossover and the mutation probabilities in order to update the search ability. After that, an exact method based on the two phase method is also developed. We have used four measuring criteria to compare these methods. The experimental results show the advantages and the efficiency of FLC-NSGA-II.     

Scheduling algorithms to minimize the number of tardy jobs in two-stage hybrid flow shops

This paper considers a two-stage hybrid flow shop scheduling problem for the objective of minimizing the number of tardy jobs. Each job is processed through the two production stages in series, each of which has multiple identical parallel machines. The problem is to determine the allocation of jobs to the parallel machines as well as the sequence of the jobs assigned to each machine. To solve the problem, a branch and bound algorithm, which incorporates the methods to obtain the lower and upper bounds as well as the dominance properties to reduce the search space, is suggested that gives the optimal solutions. In addition, two-phase heuristic algorithms are suggested to obtain good solutions for large-size problems within a reasonable amount of computation time. To show the performances of the optimal and heuristic algorithms suggested in this paper, computational experiments are done on a number of randomly generated test problems, and the test results are reported.     

带释放时间的并行机调度问题的ILS & SS算法

研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的Iterated local search(ILS)算法.1)提出了变深度环交换邻域结构.2)基于变深度环交换和传统Swap的混合邻域,提出了带有两种kick策略的ILS算法.3)为了加强ILS逃出局部最优的能力,将Scatter search (SS)搜索方法引入了ILS算法中;算法将当前最好解和次好解进行分散处理,再从处理后的解开始继续迭代.为了验证算法的有效性,对两类并行机问题分别随机产生100组数据进行试验.实验结果表明:对于同构并行机问题,引入SS的ILS算法的计算结果与下界的平均偏差为0.99%,而没有引入SS的ILS算法的为1.06%;对于无关并行机问题,引入SS搜索方法后,ILS算法的计算结果 改进了6.06%,并明显优于多点下降算法.     

A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines

Identical parallel machine scheduling problem for minimizing the makespan is a very important production scheduling problem, but there have been many difficulties in the course of solving large scale identical parallel machine scheduling problem with too many jobs and machines. Genetic algorithms have shown great advantages in solving the combinatorial optimization problem in view of its characteristic that has high efficiency and that is fit for practical application. In this article, a kind of genetic algorithm based on machine code for minimizing the makespan in identical machine scheduling problem is presented. Several different scale numerical examples demonstrate the genetic algorithm proposed is efficient and fit for larger scale identical parallel machine scheduling problem for minimizing the makespan, the quality of its solution has advantage over heuristic procedure and simulated annealing method.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

不同容量平行机下差异工件尺寸的批调度算法

在容量不同的平行批处理机环境下, 针对工件带有不同尺寸和机器适用限制的最小化制造跨度的批调度问题, 提出一种有效的蚁群优化算法. 该算法基于解的浪费空间定义启发式信息, 针对机器容量约束提出两种用于构建解的候选集, 从而有效缩小搜索空间, 并引入局部优化方法提高解的质量. 仿真实验结果表明, 所提出算法具有较好的性能, 并且优于已有的其他算法.

     

A problem space genetic algorithm in multiobjective optimization

In this study, a problem space genetic algorithm (PSGA) is used to solve bicriteria tool management and scheduling problems simultaneously in flexible manufacturing systems. The PSGA is used to generate approximately efficient solutions minimizing both the manufacturing cost and total weighted tardiness. This is the first implementation of PSGA to solve a multiobjective optimization problem (MOP). In multiobjective search, the key issues are guiding the search towards the global Pareto-optimal set and maintaining diversity. A new fitness assignment method, which is used in PSGA, is proposed to find a well-diversified, uniformly distributed set of solutions that are close to the global Pareto set. The proposed fitness assignment method is a combination of a nondominated sorting based method which is most commonly used in multiobjective optimization literature and aggregation of objectives method which is popular in the operations research literature. The quality of the Pareto-optimal set is evaluated by using the performance measures developed for multiobjective optimization problems.     

A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines

In this paper, we study a planning and scheduling problem for unrelated parallel machines. There are n jobs that have to be assigned and sequenced on m unrelated parallel machines. Each job has a weight that represents the priority of the corresponding customer order, a given due date, and a release date. An Automated Guided Vehicle is used to transport at maximum Load _max jobs into a storage space in front of the machines in a given period of time. We consider t _max consecutive periods. We are interested in minimizing the total weighted tardiness of the jobs across the periods. This measure is important when we are interested in a good on-time delivery performance. We present an appropriate mixed integer program. To solve this NP-hard problem, we develop a heuristic methodology based on decomposition and variable neighborhood search (VNS). The proposed approaches are assessed using randomly generated problem instances. We compare them with a simple heuristic based on decomposition and list scheduling using the Apparent Tardiness Cost dispatching rule. The results demonstrate that the heuristic approach based on VNS performs comparably to the mixed integer program while having reasonable solution times and outperforms the simple heuristic and a genetic algorithm (GA) from previous research.     

An ant colony-based algorithm for integrated scheduling on batch machines with non-identical capacities

In this paper, a production–distribution scheduling problem with non-identical batch machines and multiple vehicles is considered. In the production stage, n jobs are grouped into batches, which are processed on m parallel non-identical batch machines. In the distribution stage, there are multiple vehicles with identical capacities to deliver jobs to customers after the jobs are processed. The objective is to minimize the total weighted tardiness of the jobs. Considering the NP-hardness of the studied problem, an algorithm based on ant colony optimization is presented. A new local optimization strategy called LOC is proposed to improve the local exploitation ability of the algorithm and further search the neighborhood solution to improve the quality of the solution. Moreover, two interval candidate lists are proposed to reduce the search for the feasible solution space and improve the search speed. Furthermore, three objective-oriented heuristics are developed to accelerate the convergence of the algorithm. To verify the performance of the proposed algorithm, extensive experiments are carried out. The experimental results demonstrate that the proposed algorithm can provide better solutions than the state-of-the-art algorithms within a reasonable time.

     

A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines

In this paper, we discuss a flexible flow shop scheduling problem with batch processing machines at each stage and with jobs that have unequal ready times. Scheduling problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). We are interested in minimizing the total weighted tardiness of the jobs. We present a mixed integer programming formulation. The batch scheduling problem is NP-hard. Therefore, an iterative stage-based decomposition approach is proposed that is hybridized with neighborhood search techniques. The decomposition scheme provides internal due dates and ready times for the jobs on the first and second stage, respectively. Each of the resulting parallel machine batch scheduling problems is solved by variable neighborhood search in each iteration. Based on the schedules of the subproblems, the internal due dates and ready times are updated. We present the results of designed computational experiments that also consider the number of machines assigned to each stage as a design factor. It turns out that the proposed hybrid approach outperforms an iterative decomposition scheme where a fairly simple heuristic based on time window decomposition and the apparent tardiness cost dispatching rule is used to solve the subproblems. Recommendations for the design of the two stages with respect to the number of parallel machines on each stage are given.     

Weak-restriction bi-objective optimization algorithm for scheduling with rejection on non-identical batch processing machines

We investigate the problem of scheduling a set of jobs with arbitrary sizes and unequal weights on a set of parallel batch machines with non-identical capacities. The objective is to minimize the makespan of the accepted jobs and the total rejection penalty of the rejected jobs, simultaneously. To address the studied problem, a Pareto-based ant colony optimization algorithm with the first job selection probability (FPACO) is proposed. A weak-restriction selection strategy is proposed to obtain the desirability of candidate jobs. Two objective-oriented heuristic information and pheromone matrices are designed, respectively, to record the experience in different search dimensions. Moreover, a local optimization algorithm is incorporated to improve the solution quality. Finally, the proposed algorithm is compared with four existing algorithms through extensive simulation experiments. The experimental results indicate that the proposed algorithm outperforms all of the compared algorithms within a reasonable time.     

Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters

This paper addresses the problem of minimizing the scheduling length (make-span) of a batch of jobs with different arrival times. A job is described by a direct acyclic graph (DAG) of parallel tasks. The paper proposes a dynamic scheduling method that adapts the schedule when new jobs are submitted and that may change the processors assigned to a job during its execution. The scheduling method is divided into a scheduling strategy and a scheduling algorithm. We also propose an adaptation of the Heterogeneous Earliest-Finish-Time (HEFT) algorithm, called here P-HEFT, to handle parallel tasks in heterogeneous clusters with good efficiency without compromising the makespan. The results of a comparison of this algorithm with another DAG scheduler using a simulation of several machine configurations and job types shows that P-HEFT gives a shorter makespan for a single DAG but scores worse for multiple DAGs. Finally, the results of the dynamic scheduling of a batch of jobs using the proposed scheduler method showed significant improvements for more heavily loaded machines when compared to the alternative resource reservation approach.     

复杂并行机调度问题基于分解的优化算法

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题，提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题，然后针对机台选择子问题提出一种进化规划算法，并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题，以得到问题特征信息（即每台机器对应拖期工件数的最小值），该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明，本文提出的算法是有效的。     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

A new ILS algorithm for parallel machine scheduling problems

This paper addresses the non-preemptive scheduling problem of scheduling jobs on identical parallel machines to minimize the maximum completion time or makespan. The problem has been proved to be NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new methodology to obtain near-optimal solutions. We formulate the problem as an integer programming and then propose a new iterated local search (ILS) algorithm based on a variable number of cyclic exchanges to solve it. The properties of the solutions are derived and the results are used to improve the computational efficiency of our algorithm. Computational experiments show that the cyclic exchange neighborhood embedded in an iterated local search framework is effective for solving the scheduling problems with up to 1000 jobs and 40 machines within a reasonable amount of computation time. Received: April 2005 / Accepted: January 2006     

Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm

The problem of parallel machine scheduling for minimizing the makespan is an open scheduling problem with extensive practical relevance. It has been proved to be non-deterministic polynomial hard. Considering a job’s batch size greater than one in the real manufacturing environment, this paper investigates into the parallel machine scheduling with splitting jobs. Differential evolution is employed as a solution approach due to its distinctive feature, and a new crossover method and a new mutation method are brought forward in the global search procedure, according to the job splitting constraint. A specific local search method is further designed to gain a better performance, based on the analytical result from the single product problem. Numerical experiments on the performance of the proposed hybrid DE on parallel machine scheduling problems with splitting jobs covering identical and unrelated machine kinds and a realistic problem are performed, and the results indicate that the algorithm is feasible and efficient.     

A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines

This paper presents a hybrid memetic algorithm for the problem of scheduling n jobs on m unrelated parallel machines with the objective of maximizing the weighted number of jobs that are completed exactly at their due dates. For each job, due date, weight, and the processing times on different machines are given. It has been shown that when the numbers of machines are a part of input, this problem is NP-hard in the strong sense. At first, the problem is formulated as an integer linear programming model. This model is practical to solve small-size problems. Afterward, a hybrid memetic algorithm is implemented which uses two heuristic algorithms as constructive algorithms, making initial population set. A data oriented mutation operator is implemented so as to facilitate memetic algorithm search process. Performance of all algorithms including heuristics (H1 and H2), hybrid genetic algorithm and hybrid memetic algorithm are evaluated through computational experiments which showed the capabilities of the proposed hybrid algorithm.