In Nigeria, consumers resort to spontaneous change phases whenever there is power outage in any of the three phases that service their single phase meters. This lead to service transformer overload with severe consequences to domestic electrical appliances, utility firm equipments, loss of revenue due to down time and in a few cases lives. In order to reduce the frequency of these changes, a phase-constrained electricity-billing scheme for the deregulated Nigerian Power Industry was developed. This was done by re-arranging the service lines and setting up constraint matrices to relate the phase and service lines utilizable by customer to the electricity bill using penalty factors. Based on this, an algorithm with accompanying flowchart was developed; and implemented using a script file written in MATLAB environment. Results obtained for the residential (R2) class indicated that the percentage changes from the unconstrained bill to the constrained bill are 4.3% reduction for one line users, 8.6% increase for two lines users, 21.6% increase for the three lines users in the single phase category and 29.4% increase for the three phase, three lines users in the proposed system. Application of the model could help electricity regulatory authorities implement a fairer electricity billing system.