Packing programming for extravehicular missions to the space station is the process of arranging a set of missions into multiple extravehicular activities. It is an interesting combinatorial optimization problem developed from the traditional bin-packing problem. This paper first formulates a practical mathematical model that considers both the constraints of the time window for each extravehicular mission and the spacewalk time per astronaut. An Ant Colony Optimization (ACO) algorithm with a self-adaptation strategy and a new pheromone matrix characterizing the relationship between any two extravehicular missions is then proposed. The simulation results on various independent experiments show that the proposed ACO algorithm is capable of producing optimal packing programming schemes with a success rate of over 90%, which is acceptable for application to real-world problems.