最新置换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 flowtime is selected. The CDS heuristic

has a computational complexity of Om

2

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

first 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 first

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

3

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 efficient 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

4

m). The autho rs concluded that their algo -

rithm outperforms the adaptation for flowtime 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 flowtime 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 five-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 modification

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 modification significantly

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 first 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

2

m). The already mentioned RZ heuristic of Rajendran and

Ziegler [38] consists of two phases. The first 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

3

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 finally it surpasses

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

网址：最新置换Flowshop启发式算法综述：优化流程时间策略 https://www.yuejiaxmz.com/news/view/1092254

相关内容

优化算法综述
vivado 综合时间优化（多线程设置，策略选择，增量综合）
空间流线优化策略
空间换时间丶时间换空间的优化策略
电驱综合效率的计算方法与优化策略
推荐算法综述
裸金属服务器开发时间优化策略
综合服务用房设计优化策略
智能家居系统中的启动时优化算法
强化学习中的策略迭代算法优化研究

随便看看