Earth is one of the major materials used in the construction industry. Recycling earth reduces the cost of waste disposal and generates revenue for contractors. More importantly, utilizing reusable materials minimizes construction waste and reduces the environmental impact. One of the key requirements to ensure the effectiveness of earth recycling is a well-designed schedule for the movement of the dump trucks that transport earth materials to their destinations in a timely fashion. Therefore, in this study a mathematical model is developed to plan earth recycling and dump truck dispatching simultaneously from a system optimization perspective. The time-space network technique is adopted to formulate the dump truck and earth material flows in the dimensions of time and space. The model is formulated as a special multiple commodity network flow problem, which is characterized as NP-hard. To solve the real-world large-scale problems in a reasonable time, a heuristic algorithm using problem decomposition and relaxation is proposed. To suitably evaluate the model and algorithm, a case study is performed using actual parameters obtained from a large construction project in Taiwan and statistical data gleaned from government reports. The test results show that the problem can be efficiently solved and the error gap is within 0.5%. The scenario analysis indicates that the proposed framework could also be used for different problem scales. The model, coupled with the solution algorithm, has potential to serve as a planning tool for construction contractors to design optimal schedules for recycling earth materials and dispatching trucks.