This study presents a comparison of the performance of four heuristic techniques with one- and two-compartment neighbourhoods in harvest scheduling problems including a spatial objective variable. The tested heuristics were random ascent, Hero, simulated annealing and tabu search. All methods seek better solutions by inspecting the neighbourhood solutions, which are combinations that can be obtained by changing the treatment schedule in one (one-compartment neighbourhood) or two (two-compartment neighbourhood) compartments. The methods and neighbourhoods were examined in one artificial and four real landscapes ranging from 700 to 981 ha in size. The landscapes had 608 to 900 stand compartments, and the examined planning problems had 2986 to 4773 binary decision variables. The objective function was a multi-objective utility function. The spatial objective variable was the percentage of compartment boundary that joins two compartments, both of which are to be cut during the same 20-year period. The non-spatial objectives were net incomes of three consecutive 20-year management periods and the remaining growing stock volume at the end of the third 20-year period. In another problem formulation, the total harvest of the first 20-year period was used as an objective variable together with the spatial objective. The results showed that a two-compartment neighbourhood was systematically and often clearly better than a one-compartment neighbourhood. The improvements were greatest with the simplest heuristics, random ascent and Hero. Of the four heuristics, tabu search and simulated annealing proved to be the best methods, but with a two-compartment neighbourhood the differences between methods were negligible.