Reliable construction schedules are important for effective co-ordination across the supply chain and various trades at the construction work face. Reliability of construction schedules can be enhanced and improved through satisfying all potential constraints prior to execution on site. Availability of resources, execution space, execution logic, physical dependency of construction products, client instructions and others can be regarded as potential constraints. Current scheduling tools and techniques are fragmented and designed to deal with a limited set of construction constraints. In this context, a methodology termed 'multi-constraint scheduling' is introduced in which four major groups of construction constraints including physical, contract, resource and information constraints are considered to demonstrate the approach. A genetic algorithm (GA) has been developed and used for a multi-constraint optimization problem. Given multiple constraints such as activity dependency, limited working area, and resource and information readiness, the GA alters tasks' priorities and construction methods so as to arrive at an optimum or near optimum set of project duration, cost, and smooth resource profiles. The multi-constraints approach has been practically developed as an embedded macro in MS Project. Several experiments were conducted using a simple project and it was concluded that GA can provide near optimum and constraint-free schedules within an acceptable searching time. This will be vital to improve the productivity and predictability of construction sites.