A GRASP heuristic for the multi-objective permutation flowshop scheduling problem

This paper presents a multi-objective greedy randomized adaptive search procedure (GRASP)-based heuristic for solving the permutation flowshop scheduling problem in order to minimize two and three objectives simultaneously: (1) makespan and maximum tardiness; (2) makespan, maximum tardiness, and total flowtime. GRASP is a competitive metaheuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a multi-objective problem and a new algorithm named multi-objective GRASP algorithm is proposed. In order to find a variety of non-dominated solutions, the heuristic blends two typical approaches used in multi-objective optimization: scalarizing functions and Pareto dominance. For instances involving two machines, the heuristic is compared with a bi-objective branch-and-bound algorithm proposed in the literature. For instances involving up to 80 jobs and 20 machines, the non-dominated solutions obtained by the heuristic are compared with solutions obtained by multi-objective genetic algorithms from the literature. Computational results indicate that GRASP is a promising approach for multi-objective optimization.     

多工艺路线多资源多目标的作业调度优化

针对多工艺路线多加工资源多目标的作业调度问题,提出了一种启发式活动调度算法,将该方法与多目标遗传算法及模糊优选技术相结合,得到了一种新调度算法.基于工序的染色体编码方法和基于活动启发式算法的交叉算子的运用,有效地缩小了遗传算法的搜索空间.将随机产生的权系数与模糊优选技术相结合,有助于遗传算法搜索到多个优良的调度方案,这为决策者得到最满意的调度方案提供了保证.仿真结果表明该算法是可行的,与国外学者的同类研究相比,具有一定的优越性.     

Integration of simulation, design of experiment and goal programming for minimization of makespan and tardiness

This paper presents an integrated computer simulation, goal programming, and design of experiment (DOE) algorithm to solve the jobshop scheduling problem with multiple objectives. The proposed algorithm is applied to an actual textile dyeing, printing, and finishing workshop for minimization of tardiness and makespan. The simulation model enables managers to find schedule of jobs on machines given a defined combination of decision parameters which provide the smallest completion time of jobs. We then utilize DOE for determining the decision parameters to estimate the effect of both qualitative and qualitative factors through metamodeling. A goal programming model is used to find the optimum values of decision variables subject to a set of technical and managerial constraints. The proposed algorithm concentrates on two main managerial objectives simultaneously whereas previous studies are able to consider a single criterion. Finally, distinctive features of the proposed approach are compared with previous studies and models.     

流水车间作业提前/拖期调度问题研究

在非正规性能指标提前／拖期调度问题中，工件的加工顺序和每个加工活动的开始时刻都属于需要优化的变量，增加了求解的难度。针对这一问题，提出了采用分层调度模式求解流水车间提前／拖期调度问题的联合算法。首先，采用遗传算法对加工顺序进行寻优；其次，在给定调度序列的情况下采用启发式算法对加工开始时刻进行优化，制定插入机器空闲时段的策略，确定何时插入空闲时段和空闲时段的大小，即在给定顺序下确定工件加工活动的开始时刻，以满足在加工完所有工件后，使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该联合算法的有效性。     

A scheduling model for serial jobs on parallel machines with different preventive maintenance (PM)

In factories during production, preventive maintenance (PM) scheduling is an important problem in preventing and predicting the failure of machines, and most other critical tasks. In this paper, we present a new method of PM scheduling in two modes for more precise and better machine maintenance, as pieces must be replaced or be repaired. Because of the importance of this problem, we define multi-objective functions including makespan, PM cost, variance tardiness, and variance cost; we also consider multi-parallel series machines that perform multiple jobs on each machine and an aid, the analytic network process, to weight these objectives and their alternatives. PM scheduling is an NP-hard problem, so we use a dynamic genetic algorithm (GA) (the probability of mutation and crossover is changed through the main GA) to solve our algorithm and present another heuristic model (particle swarm optimization) algorithm against which to compare the GA’s answer. At the end, a numerical example shows that the presented method is very useful in implementing and maintaining machines and devices.     

Bi-objective hybrid flow shop scheduling with sequence-dependent setup times and limited buffers

The bi-objective hybrid flow shop problem with sequence-dependent setup times and limited buffers is mentioned in this paper. In this environment, there are limited buffer spaces between any two successive stages; thus, maybe there is not enough room for queues of jobs that are waiting in the system for their next operations. This problem is shown to be NP-hard in the strong sense. Up to now, some heuristic and metaheuristic approaches are proposed to minimize makespan or total tardiness of jobs. This paper presents several methods for optimization which consider two objectives simultaneously. The resolution of several specific instances from the open literature with the adaptations of non-dominated sorting genetic algorithm and sub-population genetic algorithm suggest that the proposed algorithms are effective and useful methods for solving this problem.     

The tricriteria flowshop scheduling problem

Multicriteria flowshop scheduling problems have been one of the most attractive subjects in recent years. In the multicriteria flowshop scheduling literature, a very limited number of studies have been performed on problems which include a tardiness criterion. In this paper a multicriteria (tricriteria) two-machine flowshop scheduling problem with a tardiness criterion is tackled. The objective is to minimise a weighted sum of total completion time, total tardiness and makespan. An integer programming model is proposed for the problem which belongs to NP-hard class. The modified NEH (Nawaz, Enscore and Ham) algorithm, a tabu search-based heuristic method, random search and the EDD rule (the earliest due date rule) are used to solve problems with up to 2,500 jobs. A computational analysis is conducted to evaluate the performance of the heuristics. The analysis shows that the heuristics are quite efficient, and the performance of the tabu search based heuristic is the best of all in terms of solution quality.     

A simulated annealing/local search to minimize the makespan and total tardiness on a hybrid flowshop

Scheduling is a major issue faced every day in manufacturing systems as well as in the service industry, so it is essential to develop effective and efficient advanced manufacturing and scheduling technologies and approaches. Also, it can be said that bi-criteria scheduling problems are classified in two general categories respecting the approach used to solve the problem. In one category, the aim is to determine a schedule that minimizes a convex combination of two objectives and in the other category is to find a good approximation of the set of efficient solutions. The aim of this paper is to determine a schedule for hybrid flowshop problem that minimizes a convex combination of the makespan and total tardiness. For the optimization problem, a meta-heuristic procedure is proposed based on the simulated annealing/local search (SA/LS) along with some basic improvement procedures. The performance of the proposed algorithm, SA/LS, is compared with a genetic algorithm which had been presented in the literature for hybrid flowshop with the objective of minimizing a convex combination of the makespan and the number of tardy jobs. Several computational tests are used to evaluate the effectiveness and efficiency of the proposed algorithm against the other algorithm provided in the literature. From the results obtained, it can be seen that the proposed algorithm in comparison with the other algorithm is more effective and efficient.     

Bi-objective hybrid flow shop scheduling: a new local search

In this paper, we have considered the bi-objective hybrid flow shop scheduling problem with the objectives of minimizing makespan and minimizing total tardiness. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally, and hence, heuristics are used to obtain good solutions in a reasonable time. On the other hand, local search is a method for solving computationally hard optimization problems. Hence, we introduce a novel bi-objective local search algorithm (BOLS) to solve the problem efficiently. This local search can perform an effective search in three phases. In the initial phase, the assigned job set of a machine is moved to other machines. In the second phase, the order of jobs is changed for a machine. Finally, in phase 3, a process is done to change the assigned job set of a machine and order of jobs for a machine simultaneously. A measure of performance in literature namely free disposal hull approach and a new technique proposed by authors called “triangle method” have been used to evaluate the quality of the obtained solutions. The experimental results of the comparison between the proposed algorithm and several effective algorithms show that the BOLS is attractive for solving the bi-objective scheduling problem.     

Flow shop scheduling with multiple objective of minimizing makespan and total flow time

This paper deals with the multicriterion approach to flow shop scheduling [FSS] problems by considering makespan time and total flow time. The primary concern of flow shop scheduling is to obtain the best sequence, which minimizes the makespan, flow time, idle time, tardiness, etc. In this work, makespan and total flow time of the jobs are considered for minimization. Three heuristic algorithms namely HAMC1, HAMC2 and HAMC3 have been proposed in this paper. The effectiveness of the heuristics has been analyzed using the problems generated by Taillard [16]. The results of the problems are compared with the solution procedures proposed by Rajendran [15]. The new hybrid algorithms are developed by taking the seed sequences yielded by a method proposed by Rajendran [14] in his work to minimize flow time and improving it using search algorithm. The hybrid algorithm gives better results.     

A drastic hybrid heuristic algorithm to approach to JIT policy considering controllable processing times

Job scheduling has always been a challenging task in modern manufacturing and the most real life scheduling problems which involves multi-criteria, multi-machine environments. In this research, the single-machine scheduling problem is studied in which job processing times are controllable, namely, they may vary within a specified interval. The goal of this research is to minimize total tardiness and earliness on a single machine, simultaneously. In this context, we first propose a mathematical model for the considered problem and then a net benefit compression–net benefit expansion heuristic is presented for obtaining the set of amounts of compression and expansion of jobs processing times in a given sequence. Two meta-heuristic approaches are then employed to solve medium-to-large-sized problems as local search methods. Thereafter, we apply a hybrid method based on our heuristic as well as these two meta-heuristics in order to obtain solutions with higher quality within lesser computational time. The addressed problem is NP-hard since the single machine total tardiness problem is already NP-hard. The computational results show that our proposed heuristics can effectively solve such Just-In-Time problem with a high-quality solution.     

Two-stage flow-shop scheduling problem with non-identical second stage assembly machines

This paper addresses the two-stage assembly flow-shop problem (TSAFP) with multiple non-identical assembly machines in second stage with the objective function of makespan minimization. This problem is a generalization of previously proposed problems in TSAFP. Mathematical mixed-integer linear programming model of this problem is defined, and for it being NP-hard, a hybrid SA heuristic is proposed. The heuristic is proved to solve the problem in reduced time with negligible error. To validate the proposed method, a real-life example is presented and solved in which the efficiency of the proposed heuristic is shown.     

无成组技术条件下流水车间调度的多目标优化

针对有工件组调整时间的流水车间调度问题,提出了无成组技术假设条件下的多目标优化模型,并设计了一种进化计算与局部搜索结合的混合遗传算法.模型的目标函数是最小化最大完工时间和最大拖期.在局部搜索过程中,根据问题的特征定义了两种邻域结构,采取两阶段搜索策略,以提高算法的优化搜索效率.进化过程中,采用基于个体的累计排序数和密度值的适应度分配方法,以保持群体多样性,并采取精英保留策略,以保证解的收敛性.通过测试问题和实际问题的实验以及与其他算法的比较,验证了所提模型和算法的有效性.     

A genetic-algorithm-based optimization model for scheduling flexible assembly lines

In this paper, a scheduling problem in the flexible assembly line (FAL) is investigated. The mathematical model for this problem is presented with the objectives of minimizing the weighted sum of tardiness and earliness penalties and balancing the production flow of the FAL, which considers flexible operation assignments. A bi-level genetic algorithm is developed to solve the scheduling problem. In this algorithm, a new chromosome representation is presented to tackle the operation assignment by assigning one operation to multiple machines as well as assigning multiple operations to one machine. Furthermore, a heuristic initialization process and modified genetic operators are proposed. The proposed optimization algorithm is validated using two sets of real production data. Experimental results demonstrate that the proposed optimization model can solve the scheduling problem effectively.     

Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness

This article addresses the problem of scheduling hybrid flowshops where the setup times are sequence dependent to minimize makespan and maximum tardiness. To solve such an NP-hard problem, we introduce a novel simulated annealing (SA) with a new concept, called “Migration mechanism”, and a new operator, called “Giant leap”, to bolster the competitive performance of SA through striking a compromise between the lengths of neighborhood search structures. We hybridize the SA (HSA) with a simple local search to further equip our algorithm with a new strong tool to promote the quality of final solution of our proposed SA. We employ the Taguchi method as an optimization technique to extensively tune different parameters and operators of our algorithm. Taguchi orthogonal array analysis is specifically used to pick the best parameters for the optimum design process with the least number of experiments. We established a benchmark to draw an analogy between the performance of SA with other algorithms. Two basically different objective functions, minimization of makespan and maximum tardiness, are taken into consideration to evaluate the robustness and effectiveness of the proposed HSA. Furthermore, we explore the effects of the increase in the number of jobs on the performance of our algorithm to make sure it is effective in terms of both the acceptability of the solution quality and robustness. The excellence and strength of our HSA are concluded from all the results acquired in various circumstances.     

A hybrid particle swarm optimization approach for the job-shop scheduling problem

Managing multiple projects is a complex task. It involves the integration of varieties of resources and schedules. The researchers have proposed many tools and techniques for single project scheduling. Mathematical programming and heuristics are limited in application. In recent years non-traditional techniques are attempted for scheduling. This paper proposes the use of a heuristic and a genetic algorithm for scheduling a multi-project environment with an objective to minimize the makespan of the projects. The proposed method is validated with numerical examples and is found competent.     

Parallel machine scheduling with earliness-tardiness penalties and space limits

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.     

A fitness-based weighting mechanism for multicriteria flowshop scheduling using genetic algorithms

The most effective approximate methods to tackle the problem of scheduling jobs in a permutation flowshop with the bicriteria of makespan and maximum tardiness are based on genetic algorithms (GA). In these methods, the performance of the GA is improved by applying local search to all offsprings belonging to the current population. To do so, the two objectives must be aggregated into a single objective, which is usually accomplished by weighting them into a scalar function. Since the weighting scheme is considered to be critical for the performance of the algorithm, several weighting mechanisms have been suggested in the literature. In this paper, we propose two new weighting schemes and conduct an extensive computational experience under a variety of parameter settings in order to show their effectiveness as compared to existing ones.     

基于混合粒子群优化算法的置换流水车间调度问题研究

针对最大完工时间最小的置换流水车间调度问题,提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化（hybrid particle swarm optimization,HPSO）算法。在该混合算法中,采用NEH启发式算法进行种群初始化,以提高初始解质量。运用基于随机键的升序排列规则（ranked-or-der-value,ROV）,将连续PSO算法应用于离散置换流水车间调度问题中,提出了一种基于关键路径的变邻域搜索算法,以进一步提高算法的局部搜索能力,使算法在集中搜索和分散搜索之间达到合理的平衡。最后,运用提出的混合算法求解Taillard和Watson基准测试集,并将测试结果与一些代表算法进行比较,验证了该调度算法的有效性。     

互替机床提前/延期惩罚调度问题的启发式算法

对以作业提前或延期惩罚因素之和最小为目标函数的互替机床调度问题进行了描述，提出和阐述了一种四段式启发式算法，并通过大量不同规模的问题仿真对该算法进行了评价分析，结果表明该算法可行、有效。