HYBRID HEURISTICS FOR THE PERMUTATION FLOW SHOP PROBLEM

Climate change is one of the most pressing global issues of our time,with farreaching implications for the environment,economy,and society.The effects of climate change are multifaceted and can be observed in various aspects of life on Earth.1.Environmental Impact:The most evident impact of climate change is on the environment.Rising temperatures have led to the melting of polar ice caps and glaciers, causing sea levels to rise.This not only threatens coastal cities and lowlying islands but also disrupts the habitats of many species,leading to a loss of biodiversity.Additionally, climate change has been linked to more frequent and severe weather events,such as hurricanes,floods,and droughts,which can devastate ecosystems and human settlements.2.Agricultural Effects:Agriculture is heavily dependent on stable climate conditions. Changes in temperature and precipitation patterns can lead to reduced crop yields, affecting food security globally.Droughts can decimate harvests,while floods can destroy crops and soil fertility.Moreover,warmer temperatures can shift the ranges of pests and diseases,complicating agricultural practices.3.Health Implications:Climate change can have direct and indirect effects on human health.Direct effects include heatrelated illnesses and deaths during heatwaves.Indirect effects are more complex and can include the spread of vectorborne diseases as warmer climates expand the habitats of diseasecarrying insects.Additionally,air quality can be affected by higher temperatures,exacerbating respiratory issues.4.Economic Consequences:The economic impacts of climate change are significant and varied.Industries such as agriculture,fisheries,and tourism are particularly vulnerable to the effects of climate change.Insurance costs may rise due to an increase in natural disasters,and infrastructure may require costly adaptations to withstand extreme weather events.On the other hand,some regions may experience economic benefits from a longer growing season or access to new shipping routes.5.Social and Political Ramifications:Climate change can exacerbate social inequalities and lead to political instability.Displacement of populations due to environmental disasters can create refugee crises,straining international relations and local resources. Additionally,competition for dwindling resources like water and arable land can lead to conflicts.6.Mitigation and Adaptation Efforts:In response to the impacts of climate change,there is a growing emphasis on mitigation and adaptation strategies.Mitigation involves reducing greenhouse gas emissions to slow the rate of climate change,while adaptation involves adjusting to the effects that are already occurring.This can include developingmore resilient infrastructure,investing in renewable energy,and implementing policies that promote sustainable development.cation and Awareness:Raising awareness about the impacts of climate change is crucial for driving societal and political cation plays a key role in informing the public about the science behind climate change,its consequences,and the steps that can be taken to mitigate its effects.8.International Cooperation:Addressing climate change requires a coordinated global response.International agreements,such as the Paris Agreement,aim to unite countries in efforts to reduce emissions and support those most vulnerable to climate change impacts.In conclusion,the impacts of climate change are widespread and interconnected, affecting every aspect of life on Earth.It is essential that individuals,communities,and nations work together to mitigate these effects and adapt to the changes that are already underway.。

生物多样性　1997,5(3):161～167CHIN ESE BIODIV ERSIT Y群落内物种多样性发生与维持的一个假说3张大勇　姜新华(兰州大学生物系干旱农业生态国家重点实验室,　兰州　730000)摘　要　本文根据作者对竞争排除法则的研究而提出了一个新的群落多样性假说。

按照作者的观点,占用相同生态位的物种可以稳定共存;这样,群落内物种多样性将受到4个基本因子所控制。

它们分别是:(Ⅰ)生态位的数量;(Ⅱ)区域物种库的大小;(Ⅲ)物种迁入速率,以及(Ⅳ)物种灭绝速率。

该假说强调区域生物地理过程与局域生态过程共同决定了群落内种多样性的大小及分布模式。

关键词　局域物种多样性,物种分化,区域物种库,生态位,竞争排除法则A hypothesis for the origin and maintenance of within2community species diversity/Zhang Dayong,JiangXinhu a//CHINESE BIODIVERSIT Y.—1997,5(3):161～167This paper formulates a novel hypothesis of community diversity on the basis of rejecting the competitive exclu2 sion principle.Since we accept the view that many species could occupy the same niche,local s pecies diversity is considered to be controlled by four fundamental factors,which are,res pectively,(Ⅰ)the number of niches in the community,(Ⅱ)the size of regional species2pool,(Ⅲ)species immigration rate,and(Ⅳ)species extinc2 tion rate.The hypothesis suggests that both regional biogeographic processes and local ecological processes will play an important role in determining the magnitude and pattern of community diversity.K ey w ords local species diversity,speciation,regional species2pool,niche,competitive exclusion principle Author’s address Department of Biology&State K ey Laboratory of Arid Agroecology,Lanzhou Univer2sity,Lanzhou　7300001 引言由于环境污染和生境破坏等人类活动的影响,大规模物种灭绝已成为当今社会所密切关注的一个焦点。

Heuristic approaches for the two- and three-dimensional knapsack packing problems David Pisinger and Jens EgebladTechnical Report no. 06/13ISSN: 0107-8283Dept. of Computer ScienceUniversity of Copenhagen • Universitetsparken 1DK-2100 Copenhagen • DenmarkHeuristic approaches for the two-and three-dimensionalknapsack packing problems∗Jens Egeblad and David PisingerDepartment of Computer Science,University of Copenhagen,Universitetsparken1,DK-2100CopenhagenØ,Denmark,jegeblad@diku.dk,pisinger@diku.dkDecember2006AbstractThe maximum profit two-or three-dimensional knapsack packing problem asks to packa maximum profit subset of some given rectangles or boxes into a larger rectangle or box offixed dimensions.Items must be orthogonally packed,but no other restrictions are imposedto the problem.The problem could also be considered as a knapsack problem generalizedto two or three dimensions.In this paper we present a new heuristic based on the sequencepair representation proposed by Murata et al.(1996)using a semi-normalized packing byPisinger(2006)for the two-dimensional knapsack problem.A local search algorithm main-tains a pair of sequences given as permutations of the item numbers.In each step a neighborsolution is generated by making a small permutation in one or both sequences.The newsequence pair is transformed to a packing and the corresponding objective function is eval-uated.Solutions are accepted based on a Simulated Annealing.The heuristic is also able tohandle problem instances where rotation is allowed.A similar approach with a novel abstractrepresentation of box placements,called sequence tripple,has been developed for the three-dimensional knapsack prehensive computational experiments comparing thedeveloped heuristics with previous approaches indicate that the results are very promisingfor both two-and three-dimensional problems.Keywords:Cutting and Packing,knapsack,2D knapsack,3D knapsack,sequence pair, abstract representation,heuristic,simulated annealing1IntroductionGiven a set of n rectangles j=1,...,n,each having a width w j,height h j and profit p j and a rectangular plate having width W and height H.The maximum profit two-dimensional knapsackpacking problem(2DKP)asks to assign a subset of the rectangles onto the plate such that the associated profit sum is maximized.All coefficients are assumed to be nonnegative integers,and the rectangles may not be rotated.A packing of rectangles on the plate is feasible if no two rectangles overlap,and if no part of any rectangle exceeds the plate.The maximum profit three-dimensional knapsack packing problem(3DKP)asks to assign a subset of boxes each with dimensions w j,h j,d j into a larger box with dimensions W,H and D but is otherwise similar.The problem has direct applications in various packing and cutting problems where the task is to use the space or material in an optimal way.The2DKP problem also appears as pricing problem when solving the two-dimensional bin-packing problem[4,15,16].2DKP and3DKP are NP-hard in the strong sense,which can be shown by reduction from the one-dimensional bin packing problem.Integer Programming formulations of the2DKP have been presented by Beasley[1],Hadji-constantinou and Christofides[7],and Boschetti,Hadjiconstantinou,Mingozzi[2]among others.Fekete and Schepers[4,5,6]solved the2-and3DKP through a branch-and-bound algorithm which assigns items to the knapsack without specifying the position of the rectangles.For each assignment of items a two-dimensional packing problem is solved,deciding whether a feasible assignment of coordinates to the items is possible such that they allfit into the knapsack without overlaps.An advanced graph representation was used for solving the latter problem.Pisinger and Sigurd[16]solved the2DKP through a branch-and-cut approach in which an ordinary one-dimensional knapsack problem is used to select the most profitable items whose overall area does not exceed the area of the plate.Having selected the most profitable items,a two-dimensional packing problem in decision form is solved,through constraint programming.If all items can be placed in the knapsack the algorithm terminates,otherwise an inequality is added to the one-dimensional knapsack stating that not all the current items can be selected simultaneously,and the process is repeated.Finally,Caprara and Monaci[3]developed a branch-and-bound algo-rithm for the2DKP.The algorithm is based on a branch-and-bound scheme which assigns items to the knapsack without specifying the position of each item,followed by a feasibility check. The latter is done using an enumeration scheme from Martello,Monaci,Vigo[10].In the present paper wefirst present an IP formulation of the2-and3DKP.In Section3we introduce the sequence pair representation,which we use in Section4combined with a simple local search neighborhood and Simulated Annealing to solve2DKP.In Section5we introduce a novel abstract representation of box placements in three dimensions and use the same methods as for two dimensions to solve3DKP.Finally in Section6we present our result on existing and new benchmarks instances for2-and3DKP.2Integer Programming Formulation of the problemIn the following we show an integer programming formulation of the3DKP.A formulation of 2DKP easily follows by removing variables and constraints for the third dimension.We will introduce the decision variable s i to indicate whether box i is packed within the knapsack box.The coordinates of box i are(x i,y i,z i),meaning that the lower left back corner2of the box is located at this position.If a rectangle is not packed within the knapsack we may assume that(x i,y i,z i)=(0,0,0).As no part of a packed box may exceed the knapsack,we have the obvious constraints0≤x i≤W−w i,0≤y i≤H−h i,0≤z i≤D−d i.(1)We introduce the binary decision variablesℓi j(left),r i j(right),u i j(under),o i j(over),b i j(behind) and f i j(in-front),to indicate the relative position of boxes i,j where i<j.To ensure that no two packed boxes i,j overlap we will demand thatℓi j+r i j+u i j+o i j+b i j+f i j≥1,(2)whenever s i=s j=1.Depending on the relative position of two rectangles the coordinates must satisfy the following inequalitiesℓi j=1⇒x i+w i≤x j,r i j=1⇒x j+w j≤x i,u i j=1⇒y i+h i≤y j,o i j=1⇒y j+h j≤y i,b i j=1⇒z i+d i≤z j,f i j=1⇒z j+d j≤z i.(3) The problem may now be formulated asmaxn∑i=1p i s is.t.ℓi j+r i j+u i j+o i j+b i j+f i j≥s i+s j−1i,j=1,...,nx i−x j+Wℓi j≤W−w i i,j=1,...,nx j−x i+W r i j≤W−w j i,j=1,...,ny i−y j+Hu i j≤H−h i i,j=1,...,ny j−y i+Ho i j≤H−h j i,j=1,...,nz i−z j+Db i j≤D−d i i,j=1,...,nz j−z i+D f i j≤D−d j i,j=1,...,n0≤x i≤W−w i i=1,...,n0≤y i≤H−h i i=1,...,n0≤z i≤D−d i i=1,...,nℓi j,r i j,u i j,o i j,b i j,f i j∈{0,1}i,j=1,...,ns i∈{0,1}i=1,...,nx i,y i,z i≥0i=1,...,n(4)Thefirst constraint ensures that if boxes i and j are packed,then they must be located left,right, under,over,behind or in-front of each other as stated in(2).The next six constraints are just linear versions of the constraints(3).The last three inequalities correspond to the constraints(1).The IP-model has6n2+n binary decision variables and3n continuous variables.Although the size of O(n2)binary variables is not alarming,the problem is difficult to solve.This is mainly due to the use of conditional constraints(3),as these will loose their effect when solving the LP-relaxation,and thus bounds from LP-relaxation are in general far from the IP-optimal solution.3fc e badFigure 1:A packing represented by sequence A =<e,c,a,d,f,b>and sequence B =<f,c,b,e,a,d>.3Sequence PairsMurata et al.[9]presented an abstract representation of two-dimensional rectangle packings based on sequence pairs.The problem they consider is the minimum area enclosing rectangle packing problem.In the abstract representation every compact packing can be represented by two permutations of the numbers {1,2,...,n }where each number represents a rectangle in the problem instance.The pair of permutations is called a sequence pair (A ,B ).For a given packing,the two permutations A and B are found as follows:We use the termi-nology A i j to denote that item i precedes j in sequence A .Then we have(x i +w i ≤x j∨y j +h j ≤y i )⇔A i j(5)In a similar way we use the terminology B i j to denote that item i precedes j in sequence B ,getting(x i +w i ≤x j ∨y i +h i ≤y j )⇔B i j (6)Each of the two criteria (5)and (6)define a semi-ordering,and hence for a given packing thetwo permutations A and B can easily be found by repeatedly choosing one (of possibly more)minimum elements.Figure 1illustrates a packing and a corresponding sequence pair (A ,B ).From the definitions (5)and (6)we immediately see that if item i precedes item j in both sequences,then i must be placed left of j .If i succeeds j in sequence A but i precedes j in sequence B then i must be placed under j .Formally we haveA i j ∧B i j ⇒i is left of j (7)¬A i j ∧B i j ⇒i is under j(8)where we use the terminology ¬A i j to denote that A ji .The relations (7)and (8)can be used to derive a pair of constraint graphs as illustrated in Figure 2.In both graphs the nodes correspond to the items.In the first graph we have an edge from i to j if and only if item i should be placed left of j (A i j ∧B i j ).In the second graph we have an edge from i to j if and only if item i should be placed under j (¬A i j ∧B i j ).Traversing the nodes in topological order while assigning coordinates to the items,a packing (i.e.the coordinates of the items)can be obtained in O (n 2)time.Tang et al.[18,17]showed how4the same packing can be derived without explicitly defining the constraint graph,but by finding weighted longest common subsequences in the sequence pair.Pisinger [14]further improved the algorithm,by presenting an algorithm which transforms a sequence pair to a packing in time O (n loglog n )ensuring that the packing is semi-normalized .A normalized packing is a packing where the items are packed according to the sequence B and where each new item is placed such that it touches an already placed item on its left side,and an already placed item on its lower side.A semi-normalized packing is a packing where the items are packed according to the sequence B and where each new item is placed such that it touches the contour of the already placed items both from left and from below.The difference between an ordinary packing and the semi-normalized packing is illustrated in Figure 3.The sequence pair representation makes it easy to construct a local search heuristic for pack-ing problems.In each step a neighbor solution is generated by making a permutation of two items in one or both sequences A and B .The new sequence pair is transformed to a packing and the corresponding objective function is evaluated.Based on the local search framework chosen,the new solution can be accepted,or the algorithm tries a new neighbor solution to the previous solution.4Sequence pairs for two-dimensional knapsack packingLet any sequence pair represent a legal solution to the 2DKP.To evaluate the solution we trans-form the sequence pair into a packing and add profit values for items located completely within the knapsack W ×H .This is illustrated in Figure 4.To further speed up the algorithm,we stop the transformation from sequence pair to a packing as soon as the contour of already placed items is completely outside the knapsack.For large problems where only a limited amount of items fit in the knapsack,this saves a significant part of the computational time.4.1Simulated AnnealingTo solve the 2DKP we use the metaheuristic Simulated Annealing which works well in cooper-ation with the sequence pair representation [9,18,17,14].c e fa bIfbc d Figure 2:Constraint graphs corresponding to the sequence pair (A ,B )=(<e,c,a,d,f,b>,<f,c,b,e,a,d>).Redundant edges are removed for clarity.Edges indicate which rectangles should be placed left of each other (respectively under each other).5012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849Figure 3:Transformation of a sequence pair to a packing using the ordinary transformation (left)and using the semi-normalized transformation (right)012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849Figure 4:A sequence pair (A ,B )has been transformed to a packing using the semi-normalized transformation.Only rectangles completely within the knapsack W ×H (dashed line)contribute to the profit sumIn this setting we repeatedly make a small modification to the sequence pair,evaluate the profit of the corresponding packing,and accept the solution depending on the outcome.Simu-lated Annealing is used to determine whether a solution should be accepted.An outline of the algorithm is found in Figure 5.Our variant of Simulated Annealing is as follows;At any given time the temperature is eval-uated as 1/(t 0+t s ·a )where t 0is a start time-value,t s is a time-step value and a is the number of accepted solutions.The temperature depends on the time,so the higher t 0+t s is,the lower is the current temperature.The temperature is only decreased if a new solution is accepted,since this is the only situation where the time is incremented.The neighborhood N (s )of a solution s =(A ,B )is defined as one of the following three permutations:Either exchange two items in sequence A ;exchange two items in sequence B ;or exchange two items in both sequence A and B .The items are selected randomly.6choose initial solution s∈Schoose initial time t0choose time step t sa:=0repeatchoose s′∈N(s)if f(s′)≤f(s)then accept:=true else p:=rand(0,1)T:=1f(s)if p<e−∆6y+z 548913267ABCi 13736635234765633006746339In words,C i j iff i is located right,under or in-front of j,which can be expressed as C i j⇔r i j+u i j+f i j≥1.Due to the definition of fully robot packable packings,there will always be an item which is located furthest left-over-behind.By removing this item and repeating the operation,we get the ordering of sequence A.In a similar way the orderings of B and C can be determined,as illustrated in Figure6.This shows that every fully robot packable packing can be represented by a sequence tripple.Using the relationsA i j⇔ℓi j+o i j+f i j≥1,ℓi j+r i j≤1,B i j⇔r i j+o i j+f i j≥1,o i j+u i j≤1,(12)C i j⇔r i j+u i j+f i j≥1,f i j+b i j≤1,wefind thatA i j∧B i j∧C i j⇔f i j=1A i j∧¬B i j∧C i j⇔ℓi j+r i j≥1∨o i j+u i j≥1∨f i j+b i j≥1¬A i j∧B i j∧C i j⇔r i j=1¬A i j∧¬B i j∧C i j⇔u i j=1(13)A i j∧B i j∧¬C i j⇔o i j=1A i j∧¬B i j∧¬C i j⇔ℓi j=1¬A i j∧B i j∧¬C i j⇔ℓi j+r i j≥1∨o i j+u i j≥1∨f i j+b i j≥1¬A i j∧¬B i∧¬C i j⇔b i j=1Notice that A i j∧¬B i j∧C i j and¬A i j∧B i j∧¬C i j cannot occur for any packing.We have,how-ever,chosen to assign these cases a meaning,such that every sequence tripple has a correspond-ing packing.This leads to the following four criteria,similar to(7)and(8),which are used to determine the relative box positions:A i j∧¬B i j∧¬C i j⇒i is left of j(14)¬A i j∧¬B i j∧C i j⇒i is under j(15)¬A i j∧¬B i j∧¬C i j⇒i is behind j(16)A i j∧¬B i j∧C i j⇒i is behind j(17) Notice that both(16)and(17)impose that i must be behind j in the packing.The unfortunate consequence of this is that the representation is biased towards orderings in that direction which could have a negative impact on the solution process,but as we wish to let every sequence tripple represent a packing,an arbitrary choice had to be done.5.2A Placement AlgorithmTofind a placement(i.e.the coordinates of the boxes)corresponding to a sequence tripple,we can construct three constraint graphs similar to Figure2:In thefirst graph we have an edge from item i to item j if i is located left of j(i.e.A i j∧¬B i j∧¬C i j).In the second graph we have an9edge from item i to item j if i is located under j(i.e.¬A i j∧¬B i j∧C i j).In the last graph we have an edge from item i to item j if i is located behind j(i.e.¬A i j∧¬B i j∧¬C i j or A i j∧¬B i j∧C i j). Traversing the nodes in topological order for each graph while assigning coordinates to the items, wefind the location of all boxes in time O(n2).By observing that¬B i j is a necessary criteria for node i to precede node j in each of the three constraint graphs,we may actually omit the topological ordering as it is in each case given by the reverse order of sequence B.The last box in B is placed at(x,y,z)=(0,0,0)and succeeding boxes are placed one by one according to the reverse order of sequence B.At any time let P consist of all previously placed boxes.Now assume we wish to place box i.To determine the position of i we compare i with every box j∈P.Let P x⊆P be the subset of boxes which satisfy(14),i.e.A i j∧¬B i j∧¬C i j, let P y⊆P be the subset which satisfy(15),i.e.¬A i j∧¬B i j∧C i j,and let P z⊆P be the subset which satisfy(16)or(17),i.e.¬A i j∧¬B i j∧¬C i j or A i j∧¬B i j∧C i j).Now assign i coordinates (x i,y i,z i)determined by(x j+w j))(18)x i=max(0,maxj∈P xy i=max(0,max(y j+h j))(19)j∈P y(z j+d j))(20)z i=max(0,maxj∈P zOnce a box has been placed it is inserted into P.If we maintain a table in which the position of each box i in the three sequences A,B,C is saved,we can test whether A i j,B i j or C i j holds in constant time for two given boxes i,j.Since placing a box only requires comparison with every previously placed box,calculating(18)to (20)for a given box i can be done in O(|P|)=O(n)time.Placing all n boxes then requires O(n2) time.To speed up the placement procedure slightly we remove a box from P if it is completely “shaded”by a newly inserted box.A box j is shaded by a box i if x j+w j≤x i+w i,y j+h j≤y i+h i and z j≤d j<z i+d i.5.3Simulated AnnealingTo solve3DKP we use Simulated Annealing similarly as for two dimensions but with the three-dimensional sequence representation.The neighborhood is increased to accommodate the extra sequence and consists of the following permutations:1)exchange two boxes from one of the sequences,2)exchange two boxes in sequence A and B,3)exchange two boxes in sequence A and C,4)exchange two boxes in sequence B and C,5)exchange two boxes in all sequences.6Computational ExperimentsThe heuristic described in the previous sections was implemented in C++using the sequence pair algorithm by Pisinger[14]for two dimensions and an implementation of the placement algorithm10for sequence tripple described in section5.2for three dimensions.The implementation was testedon a computer with an AMD Athlon643800+(2.4GHz)processor with2GB ram using the GNU-C++compiler(gcc4.0).This section is divided into two parts;one about2DKP and one about3DKP.6.12D Computational ExperimentsTo test the2DKP heuristic we used both the classical instances and a new set of instances.The instances were used for parameter tuning of the heuristic.Results are reported for instances both without and with rotation allowed.6.1.1Classical Instances for2DKPWe use the benchmarks instances considered by Fekete et al.[6]and Caprara and Monaci.The instances are listed in Table I.The instances beasley1-7originates from[1].The cgcut and gcut instances are guillotine-cut instances from the OR library.The instance wang20is from [19]and also a guillotine-cut instance.The instances3to CHL5are also guillotine-cut instancesby Hifi[8].Finally,the instance okp1-5are by Fekete and Schepers[5].For each instance we determine two values n0and n1.Thefirst value,n0,is defined asn0=n[Knapsack Area]/[Total area].This value should give a hint as to how many items the knapsack will contain on average in solutions.The value n1is the number of items chosen in the optimal solution for the one dimensional relaxation,as described in the sequel.We also use the value n0to determine the running time of our experiments:For an instance with n rectangles and n0defined as above let F(n,n0)=n0lg n.The idea of this function is thatif we expect there to be n0items in the knapsack then there are roughly n n0different possible solutions to search,therefore F(n,n0)should give us a rough indication of the size of solution space.The running time of each instance is determined from the value F(n,n0)of the instance,by considering the interval that F(n,n0)belongs to.Different intervals and their running times are shown in Table II.Thus the minimum and maximum running times are30and600seconds respectively.Let the one-dimensional relaxation of the two-dimensional packing problem be a one-dimensional knapsack problem where the knapsack and the items have size equal to their area,and items have profit equal to the profit of the rectangles.For all instances we consider here this problem is solved to optimum within5seconds using the exact method by Pisinger[12].The value n1is the number of items chosen in the optimal solution for the one dimensional relaxation and we use this value to set the Simulated Annealing parameters for the instance(see section6.2.1),and n1 should indicate the number of rectangles to be expected in an optimal solution.6.2New Instances for2DKPFor2DKP we have created80new instances.The rectangle dimensions in each instance belongsto one offive different classes which are listed in Table III.Thefive classes are tall(T),11Instance n0n n1beasley1 5.3205beasley2 6.3306beasley37.6504beasley4 6.53218beasley5 6.0424beasley67.86211beasley718.3626beasley88.26211beasley97.4627beasley10 6.85311beasley119.1537beasley128.61910cgcut1*10.7199cgcut2*14.83535cgcut3* 3.903535gcut1* 3.822727gcut2 4.62727gcut3* 4.6185gcut4 4.3509gcut5 4.63011gcut6 4.13011gcut7 3.7618gcut8 4.59715gcut9 4.9Table I:Literature instances for2DKP.Instances marked with’*’are used forfine-tuning of the heuristic.For F(n,n0)∈Set T(n,n0)·100][23·100,100][1,13·100,100][23.107The values can be interpreted in the following way:The higher t0and t s the less likely is ac-ceptance of a non-improving permutation.The larger the number of rectangles is in an optimal solution the more improving steps must be done before the heuristic should escape local minima by accepting a non-improving change.13Instance n0n n1 ep-30-D-C-258.310058 ep-30-D-C-7522.510092 ep-30-D-R-257.710060 ep-30-D-R-7522.510091 ep-30-S-C-257.410058 ep-30-S-C-7522.510089 ep-30-S-R-257.410060 ep-30-S-R-7522.410089 ep-30-T-C-257.410044 ep-30-T-C-7522.310084 ep-30-T-R-257.410047 ep-30-T-R-7522.410085 ep-30-U-C-257.510030 ep-30-U-C-7522.510079 ep-30-U-R-257.510031 ep-30-U-R-7522.410080 ep-30-W-C-2510.710045 ep-30-W-C-7522.310086 ep-30-W-R-2511.310050 ep-30-W-R-7522.510087 5028ep-200-D-C-2550.05045ep-200-D-C-75149.85027ep-200-D-R-2549.55045ep-200-D-R-75149.85028ep-200-S-C-2550.05044ep-200-S-C-75149.75029ep-200-S-R-2549.95044ep-200-S-R-75149.95022ep-200-T-C-2549.95042ep-200-T-C-75149.75022ep-200-T-R-2549.95042ep-200-T-R-75149.85015ep-200-U-C-2549.95039ep-200-U-C-75149.75015ep-200-U-R-2549.95040ep-200-U-R-75149.85025ep-200-W-C-2549.95043ep-200-W-C-75149.75025ep-200-W-R-2549.95043ep-200-W-R-75149.5Simulated Annealing (ep−200−S−R−75) 0.010.1 110100100010000100000T 01e−14 1e−12 1e−10 1e−08 1e−06 0.0001 0.011T step Profit Simulated Annealing (cgcut2)0.010.1 110100100010000100000T 01e−14 1e−12 1e−10 1e−08 1e−06 0.0001 0.011T step ProfitSimulated Annealing (gcut13) 0.010.1 110100100010000100000T 01e−14 1e−12 1e−10 1e−08 1e−06 0.0001 0.011T step Profit Simulated Annealing (gcut12)0.010.1 110100100010000100000T 01e−14 1e−12 1e−10 1e−08 1e−06 0.0001 0.011T step ProfitFigure 7:Results of the Simulated Annealing heuristic for different values of t 0and t s on four different instances.6.2.2ResultsBased on the parameter tuning from the previous section our heuristic was applied to the bench-mark instances described in Section 6.1.1and 6.2.To determine the robustness of the heuristic we ran each benchmark instance with 10different random seeds.We have reported the best,worst and average solution value in Table V along with the running time of each instance for each seed.The results on the 80newly proposed benchmarks are listed in Table VI and VII.The heuristic finds the optimal value in all but 4of the classical instances and on the new instances the results are generally higher than 95%of the value of the one-dimensional relaxation,which demonstrates its ability to find good solutions for both small and large instances.6.2.3RotationsWe repeated all tests allowing rotation,however we doubled the running time to accommodate for the larger solution space.A maximum time limit of 600seconds was still assigned to all instances.Parameter-tuning revealed that the same settings as reported in section 6.2.1also give good results when rotation is allowed.The results on the two sets of instances are reported in Table VIII,Table IX and Table X.For the classical benchmark instances the results with rotation are always better or as good as the results without rotation.Interestingly enough the results with rotation are generally larger than 95%of the optimal solution for the one-dimensional relaxed problem,and often they are close to 98%.For the new test instances we got slightly worse results when rotation is allowed in 32out of the 80cases.This is mainly due to the increased solution space.In only two of the instances are15Instance Optimal Best Worst Best Time Cap-Mon20116430≤0.0225323060≤0.0226624760≤0.0227526830≤0.0237335830≤0.0231728960≤0.0243043030≤0.0293883460≤0.0296292460≤0.021517145260≤0.021864168860≤0.022012186560≤0.02cgcut1244244244≤0.020.3cgcut2289228922892 1.8531.93cgcut318601860184028.24 4.586248848368300.016250059680.5300.226250061152.630 3.24625006138030376.52249854195582300.5249992236305300.1224999824014330 1.0725000024575860168.5997256939600300.08999918937349300.141000000968582.33016.31000000977670.23025.3990000008629142.72401800wang2027262716271148.41 2.722020184230≤0.022800272230≤0.022140196830≤0.023000295030≤0.022705256630≤0.0236003517.930≤0.022502232660≤0.0234103334.760≤0.0252835283240≤0.0274027402240≤0.0289988998240≤0.021393213932240≤0.02600586.560≤0.02okp127718277182748611.8311.6okp222502222142194736.411535.95okp324019240192353117.4 1.91okp43289332893328938.89 2.13okp527923279232545612.22488.27Table V:Results for the classical benchmark instances.’1D’is the result of the one-dimensional relaxed problem.’Optimal’is the value of the optimal solution.The columns under’Egeblad and Pisinger’are results of this heuristic.’Avg’,’Best’and’Worst’columns are the average,best and worst results on each instance for the10seeds.’Best Time’is the time before the heuristic discovered the best solution.’Seed Time’is the given to each of the10seeds.Thus the total running time on each instance is10times’Seed Time’.The’Exact Methods Time’represent the running time of the other methods.All running times are in seconds.For gcut13no optimal value is currently known,but we have reported the results of respectively Caprara and Monaci and Fekete and Schepers along with their upper-bound.16。

《生态翻译学视角下的汉英同传方法研究》篇一一、引言随着全球化进程的加速，汉英同声传译在跨文化交流中扮演着越来越重要的角色。

生态翻译学作为一种新兴的翻译理论，为汉英同传提供了新的研究视角和方法。

本文旨在从生态翻译学的角度出发，探讨汉英同传的方法，以期为同声传译实践提供理论支持和实际操作指导。

二、生态翻译学概述生态翻译学是一种将生态学原理与翻译理论相结合的翻译研究方法。

它强调翻译过程中的生态平衡，包括语言生态、文化生态和交际生态等多个方面。

在汉英同传中，生态翻译学要求译者关注语言转换的生态环境，保持原文与译文之间的生态平衡，实现跨文化交流的有效传递。

三、汉英同传的生态翻译学方法1. 语言生态的翻译策略在汉英同传中，语言生态的翻译策略主要体现在词汇、句法和语篇三个层面。

译者需根据上下文语境，准确理解源语信息，并运用相应的翻译技巧，如增译、减译、改译等，使译文在语言形式上与源语保持一致，实现语言生态的平衡。

2. 文化生态的翻译策略文化生态的翻译策略关注的是源语文化与目标语文化之间的差异和交流。

在汉英同传中，译者需了解两种文化的背景、价值观和思维方式等，以准确传达源语的文化内涵。

通过注解、阐释、对比等翻译方法，帮助目标语听众理解源语文化，实现文化生态的平衡。

3. 交际生态的翻译策略交际生态的翻译策略强调的是交流过程中的互动与沟通。

在汉英同传中，译者需关注交际情境、交流目的和受众特点等因素，灵活运用同传技巧，使译文在交际过程中发挥有效作用。

通过调整语速、语气和用词等，使译文更符合目标语听众的接受习惯，实现交际生态的平衡。

四、实证研究与应用分析本文通过对实际汉英同传案例的分析，探讨生态翻译学方法在同传实践中的应用。

研究发现，运用语言生态、文化生态和交际生态的翻译策略，能够有效提高汉英同传的质量和效果。

同时，结合实际案例分析，本文还提出了针对不同场景和需求的汉英同传策略和方法。

五、结论本文从生态翻译学的角度出发，探讨了汉英同传的方法。

生态学＆进化生物学词汇精选abundance多度（对物种个体数目多少的一种估测指标，多用于群落野外调查）abyssal zone深海带bathyl zone半深海带euphotic zone透光带pelagic zone浮游带，远洋带profundal zone深底带，深水层littoral zone沿岸带，滨海带 limnetic zone湖沼带，湖泊透光层intertidal zone潮间带acclimation驯化（指在实验条件下诱发的生理补偿机制，一般需时较短）acclimatisation驯化（指在自然环境条件下所诱发的生理补偿机制，通常需时较长）acquired character获得性状inheritance of acquired characters获得性状遗传adaptation适应（指生物的形态结构和生理机能与其赖以生存的一定环境条件相适应的现象）adaptive peak适应峰adaptive suite适应组合（生物对一组特定环境条件的适应必定会表现出彼此之间的相互关联性的协同适应特性）aerodynamic method空气动力法（用于测定初级生产量）aestivation夏眠 hibernation冬眠torpor 蛰伏（对恒温动物而言）diapause滞育(指某些昆虫的发育停滞) dormancy休眠age distribution年龄分布age pyramid年龄金字塔，年龄锥体age structure年龄结构increasing population增长型种群stable population稳定型种群declining population衰退型种群agglomerative method归并法agonistic behavior争斗行为altruism利他主义、利他行为（指一个个体牺牲自我而使社群整体或其他个体获得利益的行为）communication通讯行为courtship behavior求偶行为ingestive behavior索食行为parental behavior双亲行为social behavior社群行为territorial behavior领域行为atavism返祖现象atavistic regeneration返祖性再生allele等位基因allelopathy他感作用、克生作用（某些植物分泌一些有害物质，阻止别种植物在其周围生长的现象）allelopathic effects异种抑制效应，他感效应（指植物将其次生物质释放到周围环境中用以抑制别种生物的现象）allelopathic substances他感作用物质ammonification氨化作用（分解含氮有机物产生氨的生物学过程）mineralization矿化作用（微生物分解有机物质，释放CO2和无机物的过程）nitrification硝化作用（氨态氮被微生物氧化成亚硝酸，并进一步氧化成硝酸的过程）amphibian两栖动物reptile爬行动物mammal哺乳动物primate灵长类动物rodent啮齿动物arthropod节肢动物analogous organs同功器官homologous organs同源器官ancon sheep（短腿）安康羊Anthropoid类人猿anthropomorphism人神同性论（18～19世纪，即对社会和人类作神学的、形而上学的解释）antibiosis抗生（一种生物产生物质有害于一起生活的另一种生物）aposematic color警戒色（=warning coloration）protective coloration保护色mimicry拟态archeobacteria古细菌eubacteria真细菌Archeo-pteryx始祖鸟Ardipithecus ramidus始祖阿德猿、始祖南猿Australopithecus afarensis 阿法南猿Australopithecus南方古猿Homo habilis能人（“早期猿人”，早期人类第一阶段的代表）Homo erectus直立人（“晚期猿人或猿人”，早期人类第二阶段的代表）Homo sapiens智人（“化石智人”，早期人类第三阶段的代表，与现代人属同一个种）［人类起源发展的几个阶段］artificial ecosystem人工生态系统natural ecosystem自然生态系统technosphere工艺圈（指城市工业生态系统）agnosphere农艺圈（指农业生态系统）noosphere理智圈（Vernadsky,1945 定义为“人类按其意志、兴趣和利益而重新塑造的生物圈，即人类影响和控制的特殊生态系统”）association coefficient关联系数（表达种对之间是否关联。

[课外阅读]美科学家研发出“化学遗传学新技术”能操控动物行为这些受体负责发出特殊化学信号，以控制脑功能和复杂行为。

美科学家研发出“化学遗传学新技术”能操控动物行为“这种新的化学遗传学工具可能告诉我们，怎样更有效地瞄准脑回路来治疗人类疾病。

”UNC医学院蛋白质治疗与转化蛋白质组学教授布莱恩·罗斯说，“医学上面临的问题是，虽然大部分已批准的药物也能瞄准这些脑部受体，但人们还不能选择性地调节特定类型的受体以更有效地治病。

”罗斯小组早在2007年开发了第一代DREADD技术，解决了这一问题。

从本质上说，罗斯小组在实验室改变了G蛋白偶联受体的化学结构，让它能递送人工合成蛋白质，修改后受体只能由人工合成的特殊类化合物来激活或抑制，受体就像一把锁，合成药物是开锁的唯一钥匙。

这样就能按照研究目标，锁住或打开特定的脑回路以及与该受体相关的行为。

目前，世界上已有数百家实验室在用第一代DREADD 技术。

新技术只从一个方向（激活或抑制）来控制单一受体，还是第一次。

研究人员把受体装入一种病毒载体，注射到小鼠体内，这种人工受体就会被送到特定脑区、特定类型的神经元中，然后给小鼠注射人工化合药物，以此操纵神经信号将同一神经元打开或关闭，控制小鼠的特定行为。

在一类实验中，NIH的迈克尔·卡什实验室能抑制小鼠的贪吃行为；在另一实验中，UNC研究人员用可卡因和安非他明等药物诱导，也能激活类似行为。

神经元信号系统如出错，可能导致抑郁、老年痴呆、帕金森病和癫痫等多种疾病。

细胞表面受体在癌症、糖尿病等其他疾病中也起着重要作用。

新技术经改进后，还能用于研究这些疾病。

论文共同第一作者、UNC博士生埃利奥特·罗宾逊说：“这些实验证明，对那些有兴趣控制特殊细胞群功能的研究人员来说，KORD 是一种新工具，同时在治疗方面也很有潜力。

”文章来源网络整理，请自行参考编辑使用。

基于禁忌搜索算法的无等待流水车间问题求解戚海英，邱占芝（大连交通大学软件学院，辽宁大连116028）摘要：本文针对最小完工时间的无等待流水调度问题提出了一种禁忌搜索算法。

该算法首先利用调度规则构造较好的初始解，然后用禁忌搜索算法改进当前解。

在算法中采用了可达性的变邻域结构，使邻域规模小;而且对未被选中的候选解信息进行记忆，合理平衡了集中与分散搜索。

仿真结果证明该算法是有效的。

关键词：禁忌搜索；流水车间；变邻域；集中与分散搜索中图分类号：TP278Tabu search algorithms based on the no-wait Flow Shop problemsQI Haiying，Qiu Zhanzhi(Dept. of Software, Dalian Dalian jiaotong University 116028,China)Abstract: This paper presents a tabu search algorithm for solving the minimum makespan problem of Flow Shop scheduling. In the algorithm , the scheduling rule is used to create the initial solution and then the tabu search algorithm is applied to improve the last solution. The algorithm uses reachability varying neighborhood ,which is small scale ;but also Information of the unvisited candidate solutions is recollected, intensive search and dispersive search is reasonably balanced .Computer simulation experiments on the actual example show that the algorithm is applicable and effective.Keywords: tabu search ; Flow Shop ；varying neighborhood ；intensive and dispersive search0 引言无等待流水车间(no-wait Flow Shop)调度问题，也被称为同序作业调度问题，是许多实际流水线生产调度问题的简化模型，但它仍旧是一个非常复杂和困难的组合优化问题，目前对该问题的研究受到越来越多的关注。