Max-bisection　of　a　weighted　graph　G　=　(V,E)　is　to　partition　the　vertex　set　V　into　two　subsets　that　have　equal　cardinality,　such　that　the　sum　of　the　weights　of　the　edges　connecting　vertices　in　different　subsets　is　maximized.　It　is　an　NP-complete　problem.　Various　heuristics　have　been　proposed　for　solving　the　max-bisection　problem　and　some　of　them　get　very　good　quality　solutions,　but　are　time　consuming.　In　this　paper,　we　propose　several　techniques　to　speeding　up　Lin　and　Zhu’s　memetic　algorithm　for　this　problem.　It　consists　of　a　crossover　operator　with　a　greedy　strategy,　a　fast　modified　Kernighan-Lin　local　search,　and　a　new　population　updating　function.　Experiments　are　performed　on　71　well-known　G-set　benchmark　instances.　Results　show　that　the　memetic　algorithm　is　much　faster　than　Wu　and　Hao’s　memetic　algorithm,　which　can　get　best　solutions　up　to　now,　on　middle-scale　and　large-scale　instances.　Specifically,　some　current　best　known　solutions　of　the　test　instances　are　improved.　©　2015,　American　Institute　of　Mathematical　Sciences.　All　Rights　Reserved.