最新置换Flowshop启发式算法综述：优化流程时间策略

61 浏览量更新于2024-08-26 收藏 849KB PDF 举报

本文是一篇深入的研究论文，标题为“全面审查和评估置换Flowshop启发式方法，以最大程度地减少流程时间”。Flowshop是制造业中常见的生产流水线模型，其目标是优化作业在不同工作站之间的调度，以最小化流程时间或完成时间。流程时间是指所有任务从开始到完成所需的时间总和，这对于提高生产效率和降低成本至关重要。近年来，随着对Flowshop问题的关注度提升，研究人员提出了大量的启发式算法来解决该问题。启发式算法是一种寻求近似最优解而非全局最优解的方法，特别适合处理复杂且计算成本高的问题。这些算法包括各种策略，如改进的遗传算法、模拟退火、局部搜索、贪心策略等，它们在实际应用中展现了良好的性能。然而，当前的研究文献中，尽管存在一些关于此类启发式方法的综述和比较，但存在一些局限性。首先，很多现有的文献并未包含最新的研究成果，这使得最新的算法和结果难以进行全面评估。其次，缺乏统一的基准测试和计算平台，使得不同研究之间的比较具有一定的难度，很难得出一个全面的性能对比。文章的作者，来自中国东北师范大学过程工业综合自动化国家重点实验室和聊城大学计算机科学学院的Quan-Ke Pana与Rube'n Ruizc，以及西班牙瓦伦西亚理工大学的优化系统应用组，他们旨在弥补这一空白。他们通过全面的审查和评估，旨在提供一个更为全面、公正和可比的框架，以便于学术界和工业界更好地理解和应用这些启发式算法。他们的工作将涉及对最新提出的流换工作台调度算法进行详尽分析，探讨其设计原理、优缺点，以及在特定场景下的表现。此外，他们还将尝试确定哪些因素影响算法的有效性，并可能提出改进建议或者开发新的混合策略，以进一步提升流程时间的最小化效果。这篇论文为Flowshop启发式方法的研究者、工业工程师以及优化算法的开发者提供了宝贵的参考资源，对于推动该领域的发展和实践应用具有重要意义。通过阅读这篇文章，读者可以了解到如何选择合适的启发式算法，以及如何针对具体生产环境进行调整，以实现更高效的生产流程管理。

machines, each of them containing some of the original m

machines. Johnson’s algorithm is then applied to the m

1

problems

with two virtual machines and m

1

sequences are obtained. The

schedule with the minimum ﬂowtime is selected. The CDS heuristic

has a computational complexity of Om

nþ mnlogn



and research-

ers have typically used CDS as benchmark for comparisons. Gupta

[14] introduced three simple heuristics, named minimum idle time

(MINIT), minimum completion time (MICOT) and MINIMAX algo-

rithms, and compared the results against the CDS heuristic provid-

ing better results with less computational time. However, it has to

be noted that the maximum instance size tested at that time was

really small with just 7 jobs and 20 machines maximum (7  20).

Krone and Steiglitz [21] presented an early heuristic in which in the

ﬁrst phase, permutation sequences were improved by insertion

movements. In the second phase, job passing was allowed. Miyazaki

et al. [29] also presented a heuristic but in this case based on the

improvement of the sequence by the interchange of adjacent jobs.

Later, Miyazaki and Nishiyama [28] provided a similar extension

but for the additional consideration of job weights. Ho and Chang

[18] proposed a heuristic that works by minimizing the idle times

betweenjobsinthem machine case. The heuristic was evaluated

against other existing methods but mainly those proposed for

makespan minimization. Rajendran and Chaudhuri [37] introduced

three simple heuristics and compared them with those of Gupta

[14],Miyazakietal.[29] and the aforementioned heuristic of Ho

and Chang [18]. The results favored the introduced methods for the

studied instances. In a related work, Rajendran and Chaudhuri [36],

the same authors presented another heuristic that uses a lower

bound in the construction phase of the sequence. The proposed

heuristic is applied also to the no-wait problem. No comparisons

against the three heuristics of Rajendran and Chaudhuri [37]

are shown.

The NEH heuristic of Naw az et al. [32] is regarded as th e best

heuristic for the PFSP with makespan c riterion [40,39]. It is based

on the idea that jobs with larger total processing times should be

scheduled as early as possible. Consequently, the heuristic ﬁrst

generates an initial order of jobs with respect to de scending

sums of their total processing times. Then a job sequence is

constructed by evalu ating all the sequences obtained by insert-

ing a job fro m this initial order into all the possible positions of

the cur rent partial sequence. The NEH heuristic evaluates

[n(nþ1)/21] sequences and h as a complexity of O(n

m)for

the TFT criterion. Due to its effectiveness, the NEH heuristic has

been inspiring research on the total completion time criterion

since its publication. Rajen dran [35] proposed an insertion

heuristic, denoted as Raj, having many simila rities with the

NEH heuristic. The heuri stic arranges the jobs according to the

weighted total processing times and inser ts a job into a

restricted subset of all possible positions of the curren t partial

sequence. A ccording to the author’s results, the p roposed heur-

istic is more efﬁcient than the methods of Gupta [14] , Miyazaki

et al. [29] and Ho and Chang [18]. Another heuristic was

proposed by Woo and Yim [46] (denoted as WY in short). Unlike

the Raj heuristic, WY does not require an initial starting job

sequence. However, it als o has an inserti on phase where a

schedule is construct ed by inserting all non-scheduled jobs in

all possible positions of the partial sequence. This heuristic is

also based on the aforementioned NEH heuristic but has a higher

complexity of O(n

m). The autho rs concluded that their algo -

rithm outperforms the adaptation for ﬂowtime minimization of

the NEH, CDS and Raj heuristics.

Framinan et al. [10] investigated the phases of the NEH

heuristic and their contribution to its excellent performance

regarding makespan minimization. They proposed to modify the

NEH heuristic in order to accomplish total ﬂowtime criterion, and

proved that the NEH heuristic starting with an initial sequence of

jobs sorted by an increasing (instead of decreasing) sum of

processing times performs better than the adaptation of the

original NEH heuristic. It almost equals the WY heuristic in terms

of the quality of the solutions but with smaller computational

times. Later, Framinan et al. [9] further delved into the NEH

initialization and studied 177 different initial orders for the NEH,

including some specially geared towards TFT minimization.

Among the proposed methods, a heuristic called B5FT, consisting

of the best of ﬁve-tuples among the 177 approaches, is shown to

outperform the RZ heuristic of Rajendran and Ziegler [38] (to be

discussed later) and the WY method which were regarded as the

best constructive heuristics for the problem prior to the year 2000

according to Framinan et al. [11]. Framinan and Leisten [8]

presented another NEH-based heuristic, referred to as FL, with

the same complexity as the WY method. After the insertion

process in the basic NEH heuristic, the obtained partial sequence

is improved by performing a pairwise interchange improvement

procedure. If a better result is obtained, the new partial solution is

retained as the current partial sequence. Computational results

indicated that this approach outperformed RZ and WY heuristics.

More recently, Laha and Sarin [22] have presented a modiﬁcation

of the FL heuristic, denoted as FL-LS. It implements the iteration of

the insertion step of the NEH heuristic by performing job inser-

tions rather than the pairwise interchanges. The authors proved

by numerical experiments that the modiﬁcation signiﬁcantly

improves the performance of the FL heuristic while not affecting

its computational complexity.

Ho [17] presented a sorting-based heuristic that includes an

iterated improvement scheme based on job insertions and pair-

wise interchanges. The author compared the method with the

heuristics of Rajendran and Chaudhuri [37] and Raj of Rajendran

[35]. In this case, larger instances of up to 50  20 were tested and

the proposed heuristic was shown to be superior. However, this

heuristic seems closer to local search techniques such as simu-

lated annealing or tabu search rather than to constructive

heuristics as its computational effort does not make it suitable

for large problem sizes and/or in those environments where

sequencing decisions are required in a short time [11].

Other heuristics assign a weight or index to every job and then

arrange the sequence by sorting the jobs according to the

assigned index. This idea was exploited by Wang et al. [45]. The

authors presented two heuristic approaches by choosing jobs

according to a given weight or index function and appending

them to a current partial sequence. The ﬁrst one, named less idle

time rule (LIT), focuses on reducing machine idle times, while the

second one, named smallest process distance rule (SPD), focuses

on reducing both machine idle times and job waiting times. The

second approach also consists of two heuristics; one is based on

the Euclidean distance measure, while the other is based on the

linear distance. The authors did not compare their heuristics with

previous ones. Instead, they compared them against the lower

bound provided by Ahmadi and Bagchi [1]. The heuristics pro-

posed by Wang et al. [45] have a computational complexity of

O(n

m). The already mentioned RZ heuristic of Rajendran and

Ziegler [38] consists of two phases. The ﬁrst phase involves the

generation of a seed sequence according to a priority rule similar

to the shortest weighted processing time, whereas the second

phase improves the solution by carrying out a local search based

on the sequential insertion of each job in the seed sequence at

each possible different position of the incumbent partial

sequence. The RZ heuristic has a complexity of O(n

m). Compar-

isons between the RZ and WY heuristics have been performed by

several researchers [9,26]. It was found that the RZ heuristic

performs better than the WY heuristic for small-sized problem

instances but the relative performance of the WY heuristic

improves with increasing number of jobs and ﬁnally it surpasses

Q.-K. Pan, R. Ruiz / Computers & Operations Research 40 (2013) 117–128 119

剩余11页未读，继续阅读

weixin_38610657

粉丝: 3
资源: 926

最新置换Flowshop启发式算法综述：优化流程时间策略

一种新的求解置换Flowshop问题的粒子群算法.pdf

多机Flowshop调度问题

FlowshopSolveR:使用Paradiseo解决Flowshop问题的启发式方法

没有中间缓冲区的置换Flowshop调度问题的混合算法

基于基因片段分解的粒子群算法求解置换Flowshop问题

基于基因片段分解的粒子群算法求解置换Flowshop问题.pdf

FlowShop 网上花店

FlowShop.pdf

混合Flowshop调度问题

flowshop测试算例

最新资源