Abstract: The National Football League (NFL) uses numerous complex rules in scheduling regular season games to maintain fairness, attractiveness and its wide appeal to all fans and franchises. While these rules balance a majority of the features, they are not robust in spacing games to avoid competitive imbalance. We consider the scheduling of NFL regular season games and formulate a mixed-integer linear program (MILP) to alleviate competitive disadvantages originating from the assignment of bye-weeks, Thursday games and streaks of home-away games among various other sources. We propose a two-phase heuristic approach to seek solutions to the resulting large-scale MILP and conduct computational experiments to illustrate how past NFL schedules could have been improved for fairness. We also demonstrate the efficiency and stability of our approach by creating balanced schedules on an extensive set of simulated possible future NFL seasons. Our experiments show that the heuristic can quickly create a large pool of schedules that are completely free of disadvantages due to scheduling of bye-weeks and well-balanced in preparation time differences due to Thursday games.