Full opinion text
ON PETITIONS FOR REHEARING REVISED OPINION Before EDMONDSON and CARNES, Circuit Judges, and HILL, Senior Circuit Judge. CARNES, Circuit Judge: The panel hereby grants rehearing, withdraws the previous panel opinion dated May 4, 1994, and published at 20 F.3d 1489, and substitutes the following opinion: This litigation began more than twenty years ago when the United States and private parties filed civil rights complaints against the City of Birmingham, the Personnel Board of Jefferson County, and other local governmental agencies and officials. The City and the Board share responsibility for hiring and promoting local government employees. The Board, pursuant to state law, administers written tests and other job selection procedures that produce a pool of qualified, or “certified,” candidates for a particular position. See Act of July 6, 1945, No. 248, §§ 2, 16, 1945 Ala. Acts 376, 377-79, 391-92 (“Act of 1945”). The Board ranks the passing applicants and then forwards a list of the top candidates to the City for final selection. See id., § 18, 1945 Ala. Acts at 392-94 (regulating civil service appointments), amended, Act of May 4, 1989, No. 89-467, § 1, 1989 Ala. Acts 967, 967-70 (“Amendments of 1989”). The original complaints alleged, first, that the Board used discriminatory tests to determine eligibility for hiring and promotion, and second, that the City and other “employing agencies engaged in still further discrimination when selecting individuals from [the Board’s] already tainted lists.” In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) 1, 2, 1985 WL 1415 (N.D.Ala.1985). Over the past twenty years, the resulting litigation has prompted three decisions of this Court and one of the Supreme Court. This appeal stems from a recent proceeding to modify two consent decrees negotiated thirteen years ago by the original parties. In the present appeal, none of the original parties contends that the district court’s modifications were inappropriate — as far as those modifications went. Instead, the United States, joined by an intervening class of male, non-black employees of the City (the “Wilks class”), contends that the district court failed to go far enough in modifying the consent decrees to address changed circumstances. Because we agree that the Constitution requires further modifications, we reverse a portion of the district court’s order and remand for further proceedings. More specifically, we hold that the district court should: determine whether the City and the Board have a strong basis in evidence for their conclusion that race-based affirmative action is necessary in departments other than the police and fire departments, and if not, terminate the race-based goals with respect to those other departments; order the City and Board to implement valid job-selection procedures forthwith; prohibit appointments based on race or gender after valid procedures are in place, unless the district court specifically finds that further affirmative action is necessary to remedy the lingering effects of discrimination; revise the decrees’ annual appointment goals for blacks to make them flexible and reasonably related to the pool of qualified black applicants; and award appropriate attorneys’ fees to the Wilks class. Part I of this opinion sets forth the factual and procedural background of the present litigation. Part II sets forth our standards of review. Part III concerns the decree modification issues: subpart A discusses the applicable law; subpart B applies that law to the decrees’ race-conscious affirmative action provisions; and subpart C applies the law to the decrees’ gender-conscious affirmative action provisions. Part IV involves an attorneys’ fees issue. Part V concludes. I. BACKGROUND The size and complexity of this case require that we consider its history in some detail. Whenever possible, we draw on our prior decisions to summarize what has come before. A. THE COMPLAINTS, FIRST TRIAL, AND APPEAL The first six years of litigation began with a series of lawsuits against the City and Board alleging discriminatory employment practices: On January 4, 1974, the Ensley Branch of the National Association for the Advancement of Colored People, together with certain named individuals, for themselves and on behalf of others similarly situated, filed a complaint in the United States District Court for the Northern District of Alabama, against George Seibels (then Mayor of Birmingham, Alabama), the City of Birmingham, the members of the Personnel Board of Jefferson County, and the Personnel Director of that Board, alleging that the defendants engage in discriminatory hiring practices against blacks in violation of the Fourteenth Amendment, 42 U.S.C. §§ 1981, 1983, and 2000e et seq. (Title VII). A suit raising the same constitutional and statutory allegations was filed on January 7,1974, by John W. Martin and other named plaintiffs [the “Martin class”] against the City of Birmingham, Jefferson County, and the Personnel Board of Jefferson County. On May 27, 1975, the United States brought suit against the Jefferson County Personnel Board and the municipal and other governmental jurisdictions within Jefferson County alleging a pattern or practice of discriminatory employment practices against blacks and women in violation of Title VII, the Omnibus Crime Control and Safe Streets Act of 1968, as amended, 42 U.S.C. § 3766(c), the State and Local Fiscal Assistance Act of 1972, as amended, 31 U.S.C. § 1242, the Fourteenth Amendment and 42 U.S.C. § 1981. On February 20, 1976, Lucy Walker filed suit challenging the employment practices of the Jefferson County nursing home under Title VII and 42 U.S.C. § 1981. All four eases were consolidated for trial. On December 20-22,1976, trial was held on the merits of the limited issue of whether the two tests used by the Personnel Board to screen and rank applicants for positions as police officers and firefighters [were] discriminatory and violative of the constitutional or statutory rights of blacks. All other issues under the complaints were reserved until a later date. Ensley Branch, NAACP v. Seibels, 616 F.2d 812, 814-15 (5th Cir.) (footnotes omitted), cert. denied, 449 U.S. 1061, 101 S.Ct. 783, 66 L.Ed.2d 603 (1980). The police officer and firefighter tests at issue were written examinations consisting of 120 multiple-choice aptitude and knowledge questions. Ensley Branch, NAACP v. Seibels, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6797 & n. 16, 1977 WL 806 (N.D.Ala.1977), aff'd. in part and rev’d in part, 616 F.2d 812 (5th Cir.), cert. denied, 449 U.S. 1061, 101 S.Ct. 783, 66 L.Ed.2d 603 (1980). The score required to pass each test varied with the number of vacancies and other factors. Ensley Branch, 616 F.2d at 816 n. 10. Under procedures still in place today, the Board ranks passing applicants on an eligibility list according to their score. Id. at 816. For promotional positions, an applicant’s score is increased by one point for each year of seniority. See Act of 1945, § 20,1945 AIa.Acts at 394-95; accord In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) 1, 5, 1985 WL 1415 (N.D.Ala.1985). When a vacancy arises, the Board forwards the top three names from the eligibility list to the City for final selection. See Act of 1945, § 18, 1945 Ala. Acts at 392-94, amended, Amendments of 1989, § 1, 1989 Ala. Acts at 967-70; accord 37 Fair Empl.Prac.Cas. (BNA) at 5 & n. 12. As discussed below, the district court in 1981 approved a pair of consent decrees requiring the City and Board to modify their procedures to take into account race and gender as well. Ironically, the firefighter and police officer tests challenged in the original trial were themselves adopted, or at least modified, for the specific purpose of hiring more blacks. As the district court explained: In late 1965, following an independent study as to why no blacks were then employed as police officers in the City of Birmingham, the Personnel Board decided to replace its police and firefighter exams with tests developed by the Public Personnel Association, now known as the International Personnel Management Association. IPMA tests were being widely used in other parts of the country and were considered by the Board as superior to other tests then available. The change was part of a multi-faceted program intended to increase black participation in governmental positions. Ensley Branch, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6795. On the advice of consultants that some test questions were more predictive than others of blacks’ future job performance, the Board in 1974 began to use a new scoring key that was designed to “increase validity of the [police officer] test for black applicants.” Id, The Board also began actively to encourage blacks to apply, to waive examination fees, to experiment with reducing the passing score for the police officer test, and to eliminate priority for applicants residing within the employing agency’s jurisdiction. Id. at 6795-96. After assessing these efforts to increase black employment, the district court concluded that the Board’s “selection, administration and use” of the two tests had not been motivated by a “design or intent ... to discriminate on the basis of race or color” and therefore did not violate the Equal Protection Clause. Id. at 6796. The plaintiffs did not appeal that finding. Ensley Branch, 616 F.2d at 815 n. 5. The district court also found, however, that the police officer and firefighter tests violated Title VIL The court noted that both tests had a significant adverse impact on black applicants, a phenomenon defined as a passing rate “less than four-fifths ... of the rate for [whites].” Ensley Branch, 13 Empl. Prac.Dec. (CCH) ¶ 11,504, at 6796-97 (internal quotation marks omitted). The court ruled that the tests could be used only if, despite their adverse impact, they were sufficiently “job related” to predict effectively test takers’ future job performance. Id. at 6796 nn. 10-11, 6806. After reviewing testing data, the court concluded that the tests failed to meet this standard. Id. at 6798-6808. The court found no statistically significant correlation between the applicants’ scores on the firefighter test and their later job performance. Although there was a significant positive correlation between test scores and job performance during the first three years of a firefighter’s service, the court found a significant negative correlation between test scores and job performance after the first three years. Id. at 6803. To the court, these findings “suggested] that over time the lower scoring applicants made the better employees.” Id. Thus, “one is hard pressed to conclude that the higher scoring [firefighter] applicants are in fact the better persons to hire.” Id. The district court analyzed the police officer test somewhat differently. Operating under the assumption that supervisor bias had not influenced black officers’ perfor-manee ratings, id. at 6802, the district court found a statistically significant correlation between black police officers’ test scores and their later job performance, id. at 6803. Nevertheless, the district court concluded that “the magnitude of the positive prediction is so low that the test is worthless for all practical purposes.” Ensley Branch, 616 F.2d 812, 818 n. 16 (5th Cir.), cert. denied, 449 U.S. 1061, 101 S.Ct. 783, 66 L.Ed.2d 603 (1980). Among its many detailed findings, the district court determined that “use of the test predicts [job performance] with a margin of error that is only 2% smaller than it would be without the test.” Ensley Branch, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6804. The court also found the test could not predict with a reasonable degree of certainty whether any one applicant would actually perform better than any other. Id. at 6805. The district court therefore concluded that the tests were not sufficiently “job-related” to satisfy Title VII, 42 U.S.C. § 2000e-2(h). Id. at 6806-08; see generally Albemarle Paper Co. v. Moody, 422 U.S. 405, 425, 95 S.Ct. 2362, 2375, 45 L.Ed.2d 280 (1975) (“Title VII forbids the use of employment tests that are discriminatory in effect unless the employer meets ‘the burden of showing that any given requirement [has] ... a manifest relationship to the employment in question.’” (quoting Griggs v. Duke Power Co., 401 U.S. 424, 432, 91 S.Ct. 849, 854, 28 L.Ed.2d 158 (1971)). As a remedy for the Board’s use of illegal tests, the district court ordered race-conscious relief “[p]ending adoption of some selection procedure which either has no adverse effect upon black applicants or is sufficiently job-related.” Ensley Branch, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6808. The district court: ordered that blacks be referred for openings on the police and firefighter forces at the rate at which they took the tests when most recently administered. To accomplish this, the Court ordered that the names of a sufficient number of blacks be added to the current police and firefighter eligibility lists [which included passing applicants from the most recent test administration] so that the lists shall be representative of the racial composition of the test-takers [at that most recent test administration], i.e., 28 and 14 percent black for police and firefighter ■ lists, respectively; that, one-third of future certifications, i.e., referrals from the [existing eligibility] lists for actual employment, are to be black until, considering all certifications since the relevant 1975 and 1976 dates [when the Title VII violations began], the numbers of certifications become representative of the racial composition of the test-takers [at the most recent test administration]. Thereafter, blacks are to be certified in accordance with their representation on the lists, i.e., 28 and 14 percent of certifications for policemen and firefighters, respectively, will be black. Similarly, referrals from future [eligibility] lists [created by future test administrations] will be a function of the rate at which blacks take the examinations on which the lists are based, until or unless defendants develop valid tests. Ensley Branch, 616 F.2d at 815 n. 6. An appeal and cross-appeal ensued. The Board appealed the district court’s decision that the police and firefighter exams violated Title VII. Id. at 815. In doing so, the Board did not contest the district court’s finding that the two tests had an adverse impact, but contended that the tests were in fact job-related. Id. at 816. We upheld the district court’s finding that the Board had faded to validate either exam, and affirmed the district court’s holding that use of the two exams violated Title VII. Id. at 818, 822. The United States and the Martin class of black plaintiffs jointly cross-appealed the district court’s holding that use of the tests did not begin to violate Title VII until the dates on which the negative results of the test validation studies were reported to the Board. Id. at 815, 823. The district court had reasoned that, until the final results were reported, the Board was justified in using the tests in anticipation of favorable results from the validation studies. Id. at 823. On appeal, we inferred that the district court had relied on an Equal Employment Opportunity Commission guideline that, in “ Very limited circumstances,’ ” authorized a local government to use tests pending the results of a validation study. Id. (quoting Albemarle Paper C.o., 422 U.S. at 436, 95 S.Ct. at 2380). However, because we could not determine from the district court’s findings whether the case presented one of those “very limited circumstances,” we remanded for additional fact finding. Subsequent events obviated the need for those findings, which were therefore never made. B. THE SECOND TRIAL, CONSENT DECREES, AND APPEAL While the first appeal was pending, the district court conducted a second trial. That trial involved challenges to other Board practices, including: written tests for eighteen more positions; various rules affecting promotional opportunities; the imposition of height, weight, and educational requirements for certain jobs; and the restriction of some job announcements and certifications to persons of a particular sex. United States v. Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) 1834, 1835, 1981 WL 27018 (N.D.Ala.1981), aff'd, 720 F.2d 1511 (11th Cir.1983). The Board defended on the grounds that these practices either had no adverse impact upon blacks or women, or were sufficiently job-related to be effective predictors of future job performance. Id. As in the first trial, the City did not participate. In fact, the original plaintiffs’ claims against the City never reached trial. While the first proceeding was on remand and the second was at trial, the parties entered settlement talks that eventually suspended both proceedings. Once again, we resort to our summary of the facts from a prior decision: After we ruled on the district court’s decision concerning the written [police officer and firefighter] tests, [Ensley Branch, 616 F.2d at 812], the plaintiffs, in all three cases, entered into extensive negotiations with the Board and the City which culminated in two proposed consent decrees, one with the Board and one with the City. The former disposed of all of the plaintiffs’ claims against the Board; the latter disposed of all the plaintiffs’ claims against the City. United States v. Jefferson County, 720 F.2d 1511, 1514-15 (11th Cir.1983) (footnotes omitted). Thus, before the district court ruled on the remand of the first case or rendered a decision in the second case, the parties submitted proposed consent decrees that settled all claims against the City and the Board, including allegations of gender discrimination raised by the United States. Although these decrees provided retrospective relief such as back pay for some individuals, their keystone was an extensive regime of affirmative action for blacks and women. At the heart of the Board decree was a requirement, subject to the availability of qualified applicants, that the Board annually certify blacks and women either according to racial and gender quotas set forth in the decree or in proportion to their representation in the applicant pool, whichever was higher. The decree’s minimum certification rates ranged from ten to fifty percent, depending on the position involved and whether the goal applied to blacks or women. The Board agreed to continue to certify according to these annual “goals” until satisfaction of the long-term “goal”; i.e., until the proportion of blacks and women employed by the City in any given job classification “approximate[d] the respective percentages [of blacks and women] in the civilian labor force of Jefferson County.” These provisions did not govern appointment of blacks to entry-level police and firefighter positions, with respect to which the Board decree simply adopted the remedies established by the district court’s 1977 order on that subject. Nor did the decree state that the development of lawful selection procedures would terminate race- and gender-conscious certification requirements, which could potentially have continued forever. The Board decree established several other significant obligations. First, the Board committed itself “periodically” to review its hiring and promotion procedures to ensure that the procedures either had no adverse impact or were sufficiently job-related to pass muster under Title VII. Second, so long as the Board’s procedures — whether job related or not — had a disparate impact on blacks or women, the Board agreed to “mak[e] a good faith effort to determine whether there [were] any alternative [testing procedures] ... which [would] reduce any adverse impact.” Third, the decree prohibited the Board’s prior practice of restricting job announcements on the basis of gender. Fourth, the decree mandated continued aggressive recruitment of blacks and women. In broad outline, the City decree was quite similar to the Board decree. It too established annual “goals” for hiring and promoting blacks and women and a “long term goal” of parity between the proportion of blacks and women in any City job classification and the proportion of blacks and women in the civilian labor force. With a few exceptions, the annual goals required the City to hire and promote blacks and women either according to racial and gender quotas set forth in the decree, or at the rate of black and female representation in the applicant pool, whichever was higher. The City also agreed to request the Board “selectively to certify ... qualified blacks and females whenever ... necessary to provide the City with a certification list that contains sufficient numbers of blacks and females to meet the [decree’s] goals.” As with the Board decree, the City decree’s annual goals were “subject to the availability of qualified ... applicants.” In addition, the parties reserved the right: to adjust, through agreement and subject to the approval of the Court, any of the goals provided by this Decree where it can be shown that a professional degree, license or certificate is required to perform the duties of any particular job or jobs in the City’s workforce and that blacks and/or women hold such degrees, licenses or certificates in percentage terms which are inconsistent -with the goals provided. The decree also stated that “[n]othing herein shall be interpreted as requiring the City ... to hire, transfer, or promote a person who is not qualified, or to hire, transfer or promote a less qualified person, in preference to a person who is demonstrably better qualified based upon the results of a job related selection procedure.” Other provisions obligated the City to strengthen its recruitment of blacks and women, prohibited any restriction of jobs by gender, and eliminated time-in-grade requirements for some promotional positions. Although the consent decrees resolved the issues as between the parties to the original cases, several interested non-parties soon appeared to challenge the decrees, claiming that the decrees would adversely affect their employment opportunities. Chief among the objectors was the Birmingham Firefighters’ Association (“BFA”), a labor association representing a majority of City firefighters, most of whom were white males. We return to our previous narrative for a description of the ensuing conflict: The [district] court provisionally approved these consent decrees in June 1981, but reserved final approval until it convened a fairness hearing to consider the objections of all interested parties. The court held that hearing in August 1981, at which it considered, among others, the objections filed by the Birmingham Firefighters Association 117 (BFA), as amicus curiae. The day after the hearing, BFA and two of its members (BFA members) moved ... to intervene of right in each of the three cases, contending that the proposed consent decrees would have a substantial adverse impact upon them. The court denied their motions as untimely, and approved, and entered, both consent decrees. Jefferson County, 720 F.2d at 1515 (footnote omitted). Before approving the decrees, the district court rejected the merits of the objections raised at the fairness hearing by the would-be intervenors. The district court reasoned that the decrees “[did] not preclude the hiring or promotion of whites or males,” Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) at 1836, and that the City’s hiring goals were “expressly made subject to the caveat that the [City] decree is not to be interpreted as requiring the hiring or promotion of a person who is not qualified or of a person who is demonstrably less qualified according to a job-related selection procedure,” id. at 1837. The court further noted that the “provisions for potentially preferential treatment [were] limited both in time and in effect” because they would expire on their own terms when the work-force parity goals were met and because either decree could “be dissolved after a period of six years” if the purposes of the decree had been substantially achieved. Id.; see also In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) 1, 3 n. 5, 1985 WL 1415 (N.D.Ala.1985) (describing the circumstances in which the decrees may be dissolved). In addition, the court reviewed the evidence of past discrimination against blacks and women and concluded that “there is more than ample reason for the Personnel Board and the City of Birmingham to be concerned that they would be in time held liable for discrimination” against blacks seeking promotional positions in the police and fire departments and against woman at all levels of hiring and promotion in those departments. Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) at 1838. On appeal, this Court affirmed the district court’s denial of the BFA’s intervention motion. Jefferson County, 720 F.2d at 1516-19. Shortly after the district court approved the decrees and denied leave to intervene: Seven individual white male firefighters ... filed a complaint in the district court against the Board and the City to enjoin the enforcement of the consent decrees on the ground that the operation of the decrees would discriminate against them in violation of Title VII of the Civil Rights Act. They applied for a preliminary injunction, which, after a hearing, the district court denied. Jefferson County, 720 F.2d at 1515 (footnote omitted). In the same opinion in which we affirmed the denial of the BFA’s motion to intervene, we also upheld the district court’s denial of the preliminary injunctive relief sought by the seven individual white male firefighters. Id. at 1520. C. THE REVERSE DISCRIMINATION LITIGATION The district court’s approval of the consent decrees, and our refusal to allow the BFA to intervene, brought forth a collection of cases that has come to be known as the “Birmingham Reverse Discrimination Employment Litigation.” In these cases, a number of male, non-black City employees collaterally attacked the decrees and the affirmative action programs adopted under them. See In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d 1492, 1495 (11th Cir.1987), aff'd sub nom. Martin v. Wilks, 490 U.S. 755, 109 S.Ct. 2180, 104 L.Ed.2d 835 (1989). The United States, despite its status as a signatory of the consent decrees, also brought suit against the City, lodging allegations similar to those of the individual plaintiffs. Id., 833 F.2d at 1496; cf. In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) 1, 8, 1985 WL 1415 (N.D.Ala.1985) (permitting the United States to side with the reverse discrimination plaintiffs on the issue of whether the City was violating the decree). These cases were heard by the same judge who had heard the earlier consent-decree cases. Prior to trial, the district court rejected the reverse discrimination plaintiffs’ collateral challenge to the legality of the decrees. See In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) at 3 & n. 6. Instead, the district court restricted the plaintiffs’ action to the questions of whether the City or the Board had violated the decrees or had granted illegal preferences that were not required by the decrees. Id. at 3-4. At the close of the plaintiffs’ ease, the court further limited the action by dismissing for lack of evidence all claims against the Board. See Martin v. Wilks, 490 U.S. 755, 779 n. 16, 109 S.Ct. 2180, 2194 n. 16, 104 L.Ed.2d 835 (1989) (Stevens, J., dissenting). This left the City as the only defendant. At trial, the plaintiffs had claimed that some blacks were promoted over more-qualified non-blacks despite the fact that the City decree specifically did not require the City to “promote a less qualified person, in preference to a person who is demonstrably better qualified based upon the results of a job related selection procedure.” After trial, the district court found for the City, holding that the City had shown that its employment actions were required by the decrees. Id. at 780-81, 109 S.Ct. at 2194-95. The district court in effect decided that the provision quoted by the plaintiffs applied only if job related selection procedures were in place. In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d at 1497. Although the district court agreed that “[m]ost but not all of those whites who were not selected for [the challenged promotions] had higher test scores” than the blacks who were selected, the court pointed out that the tests on which these scores were based had never been shown to be valid predictors of future job performance. The court further noted that the City “ ‘does not use a job-related selection procedure in evaluating the qualifications of certified candidates [and] has made no effort to develop ... such a procedure.’ ” In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d at 1497 (quoting the district court’s December 26, 1985, order (emphasis and alteration added)). Accordingly, the district court rejected the plaintiffs’ assertion that demonstrably better qualified whites had been passed over. On appeal, this Court reversed. We observed that “the district judge treated the plaintiffs as if they were bound by the consent decrees,” rendering the plaintiffs unable to challenge the decrees’ validity, and limiting their action to a claim that the City had granted racial preferences beyond those mandated by the City decree. Id. at 1496. This limitation was unfair to the male, non-black plaintiffs, we reasoned, because they had not participated in the negotiation or signing of the consent decrees. Id. at 1498-99. To give the reverse-discrimination plaintiffs their day in court, we ruled that they must be allowed to bring an action challenging the validity of the decrees. Id. at 1499-1500. We therefore directed the district court to re-examine the legality of the decrees under the heightened scrutiny applicable to voluntary government affirmative actions plans. Id. at 1500-01. Finally, we ruled that the United States was estopped from collaterally attacking the decrees by its status as a signatory. Id. at 1501. “[I]f the United States believes that the decrees should be modified based on changed circumstances, its remedy ... is to seek modification in the court which retained jurisdiction over the cases in which the decrees arose.” Id. at 1501. Our decision' was upheld by the Supreme Court in Martin v. Wilks, 490 U.S. at 769, 109 S.Ct. at 2188. In affirming our reasoning, the Wilks Court implicitly suggested that plaintiffs in future eases could avoid such collateral challenges by insuring that all interested parties were joined from the outset. See id. at 765-67, 109 S.Ct. at 2187. The district court subsequently held a new trial on the reverse discrimination plaintiffs’ challenge. At the conclusion of that trial, the district court again ruled in favor of the City. Bennett v. Arrington, 806 F.Supp. 926, 931 (N.D.Ala.1992). Applying strict scrutiny, id. at 928, the district court found that the City had “significant evidence” of past discrimination to support its affirmative action program. Id. at 929. The court further found the affirmative action provisions were narrowly tailored because the City had first tried alternative measures, and because these provisions were both flexible and temporary. Id. at 929-30. That ruling was recently reversed by another panel of this Court. See In re Birmingham Reverse Discrimination Employment Litig., 20 F.3d 1525 (11th Cir.1994). D. THIS DECREE MODIFICATION PROCEEDING After we suggested that the United States could not collaterally challenge the decrees but could seek modifications, see In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d at 1501, the parties began discussing modification as a possible means of resolving their outstanding differences. With that prospect in mind, the plaintiffs from the reverse-discrimination case moved to intervene in this, the original consent-decree, ease and to consolidate this case with the reverse-discrimination case. On May 25, 1990, the district court denied the reverse-discrimination plaintiffs’ motion to consolidate, but allowed them to intervene in this case “for the limited purpose of participating in any litigation regarding potential modification of the consent decrees.” Subsequently, in an effort to gather all interested parties in a single proceeding, the district court certified both a class of “[a]ll present and future black and female employees ... [and] applicants for employment with the City” (the “Bryant class”), and a class, represented by several of the plaintiffs from the parallel reverse-discrimination case, of “[a]ll present and future male, non-black employees ... [and] applicants for employment with the City of Birmingham” (the “Wilks class”). On May 3, 1990, the United States moved to modify the consent decrees. The United States urged the district court: (1) “to replace the existing long-term goals (which [were] ... based on civilian labor force figures) with the long-term goal of developing lawful selection procedures”; (2) “to replace the current interim goals with interim goals based on applicant flow data” that would terminate upon the implementation of lawful selection procedures; (3) “to require the Personnel Board to develop nondiscriminatory selection procedures in a timely manner ... ”; (4) “to require the City of Birmingham to cooperate with the Board in the Board’s efforts to develop nondiscriminatory selection procedures and for the City to demonstrate that any selection procedures it has implemented in addition to those of the Personnel Board, are lawful”; and (5) “to strengthen the current recruitment mechanisms.” In an accompanying proposed order, the United States requested the court to give the Board three years to develop lawful tests and to require the Board to stop crediting applicants with seniority points to the extent that use of such points violated Title VII. The United States asserted that “[t]hese modifications are appropriate in light of changed circumstances, emerging case law, and the experience of the parties under the decrees over the past nine years, and to move this matter toward a conclusion where continuing court jurisdiction will no longer be required.” The Wilks class soon submitted its own modification proposals, which requested the court: (1) to vacate all long-term and annual goals; (2) to enjoin the City and Board from making employment decisions based solely on race or gender; and (3) to terminate both the decrees and all court supervision of City and Board employment practices within four years. The City, the Bryant class of blacks and women, and the Board filed responses to these modification motions in July 1990. For its part, the City “acknowledge^] that limited modification ... [was] appropriate because of changed circumstances,” including the City’s achievement of some of its long-term goals and the fact that “the selection procedures employed by the Personnel Board continue to have an adverse impact upon blacks and have not been demonstrated to be valid selection procedures.” With these developments in mind, the City proposed the following modifications: (1) “Where long term goals have been met, but selection devices which create an adverse impact on blacks remain ..., replace the current interim annual goals [based on fixed percentages set out in the City decree] with interim annual goals based on representation in the qualified applicant pool.” (2) “Modify long term goals which are demonstrated to be inconsistent with the qualified applicant pool to reflect representation of the qualified pool,” rather than representation in the general labor force. (3) Terminate the Decree, “in whole, or in part by job classification[ ], upon motion of any party, and a finding by the Court that a lawful selection procedure is in place for appointment to that job classification and the long term goal for such classification(s) has been achieved.” The Bryant class of blacks and women joined in these recommendations and also agreed with the United States that “a reasonable timetable should be established” for the development of lawful selection procedures by the Board. The Board, too, accepted the need to develop lawful tests, but vehemently opposed the United States’ proposed three-year timetable as both unrealistic and unnecessary. The Board rested its contention that a timetable was unnecessary on its assertion that it had already made significant progress toward eliminating adverse impact from its selection procedures. The Board also opposed the United States’ call for an end to seniority-point enhancements, noting that the federal guidelines on enforcement of Title VII do not disallow the use of seniority points. Cf. 42 U.S.C.A. § 2000e-2(h) (1981 & Supp.1993) (“[I]t shall not be an unlawful employment practice for an employer to apply different standards of compensation, or different terms, conditions, or privileges of employment pursuant to a bona fide seniority or merit system _”). After holding a hearing on these issues, the district court ordered several modifications to the decrees. The court began by noting that the decrees had: in conjunction with a city administration whose ... leaders have reflected the majority-black voting population within the city, served to reduce, if not eliminate, discriminatory employment practices against blacks and females and, indeed, to enhance the opportunities of such persons for employment and promotion. Nor can it be denied that, in so doing, the decrees have impaired some employment or promotional opportunities of whites and males In the police and fire departments, the two departments at the core of the original litigation, black employment had more than doubled, from twenty to forty-one percent in the Police Department and from ten to twenty-six percent in the Fire Department. The percentage of blacks and females in many promotional positions had also increased significantly. Overall, forty-five percent of the City’s full-time employees were black and twenty-three percent were female as of September 1990. Blacks and women held jobs in approximate proportion to their presence in the general labor force for about half of the City’s classified positions. After reciting these facts, the district court noted that “[a]ll parties agree that some modifications have become appropriate.” Guided by its view of the underlying purposes of the decrees, remedying past and preventing future discrimination, the district court ordered the following modifications to the City decree: (1) The City must stop using annual goals for any particular job classification once the long-term goal for that classification is met. (2) The City must stop using annual goals for any promotional position once the long-term goal is met for the position from which the promotional candidates are normally chosen, except that the City should continue to promote blacks and women to high-level police and fire positions in proportion to those groups’ representation in the position from which promotions are normally made until the long-term goal is reached with respect to the high-level positions. (3) The City must stop using annual goals for any particular job classification once the Board develops lawful screening procedures for that job. (4) The City should group similar jobs together for the purpose of determining whether a particular goal has been met. (5) The district court will, in 1996, reconsider the appropriateness of continuing the City decree. The district court made only one modification to the Board decree. This modification requires that, until the Board develops a lawful test for a particular position, it must, at the City’s request and subject to the availability of qualified applicants, certify black and female candidates for that position in proportion to their representation among applicants — even after the City has met its long-term goal (and thus has stopped following the annual goal) for that position. The district court viewed this modification as necessary to avoid a situation in which the City would be obligated to “appoint or promote only on the basis of certifications made from [the] discriminatory testing devices employed by the Personnel Board.” The district court acknowledged that long-term goals tied to black and female representation in the general labor force “do[] not provide an accurate estimate of the pool of persons potentially qualified” for particular City jobs. As a result, the court conceded that these goals “would not pass muster under current legal standards as a valid measure of a discrimination-free job force.” However, noting that the long-term goals were “largely hortatory,” the court said that the consequences of this “potentially inappropriate measure” would be “partly reduced” by other modifications to the City decree. The court therefore declined to rewrite the decrees’ “inherently suspect” long-term goals to reflect the proportion of qualified blacks and women in the relevant labor pool. The court also refused to impose deadlines on the Board for the development of lawful selection procedures that would displace the long-term goals. The court agreed that the “use of such testing procedures would be desirable,” but reasoned that specific development and review requirements “would be unrealistic, unworkable, and unwise” — “particularly if accompanied by a judicially-imposed timetable.” Finally, the district court rejected the United States’ request for an order mandating strengthened recruitment of blacks and women because the parties were already “in general agreement” that recruitment efforts should be increased. After the district court issued its initial modification order, the Wilks class moved for an interim award of attorneys’ fees for its efforts in both the parallel, reverse-discrimination case and the modification proceeding. The class argued that the court’s modification order meant that the class had, in part, prevailed in both cases. The district court denied the request, but expressly permitted the class to renew its application in the reverse-discrimination case. Both the United States and the Wilks class now appeal. The United States claims that the district court abused its discretion in rejecting any requirement that the City and Board develop lawful, nondiscriminatory selection procedures to replace the existing numerical goals. The Wilks class takes a bolder position, arguing that there is insufficient evidence of past discrimination to give the City and Board a compelling interest in any affirmative action plan. In addition, both the Wilks class and the United States argue that the decrees’ appointment goals fail the narrowly tailored test, established by City of Richmond v. J.A. Croson Co., 488 U.S. 469, 109 S.Ct. 706, 102 L.Ed.2d 854 (1989), because these goals are tied to general labor force statistics rather than to a more accurate measure of the pool of qualified applicants. Finally, the Wilks class challenges the district court’s denial of fees and its refusal to accept certain deposition testimony in evidence. The City, the Board, and the Bryant class contend on appeal that the district court orders were within the district court’s discretion and should be affirmed in their entirety. II. STANDARDS OF REVIEW We review for abuse of discretion a district court’s modification of, or refusal to modify, a consent decree. System Fed’n No. 91 v. Wright, 364 U.S. 642, 648, 81 S.Ct. 368, 371, 5 L.Ed.2d 349 (1961); Jacksonville Branch, NAACP v. Duval County Sch. Bd., 978 F.2d 1574, 1578 (11th Cir.1992). At the very least, a district court abuses its discretion if it refuses to make modifications required by applicable law. See Firefighters Local Union No. 1784 v. Stotts, 467 U.S. 561, 573-83, 104 S.Ct. 2576, 2585-90, 81 L.Ed.2d 483 (1984); cf. Rufo v. Inmates of Suffolk County Jail, — U.S. -, -, 112 S.Ct. 748, 762, 116 L.Ed.2d 867 (1992) (“A consent decree must of course be modified if, as it later turns out, one or more of the obligations placed upon the parties has become impermissible under federal law.”). We also review for abuse of discretion a district court’s exclusion of evidence and denial of attorneys’ fees. U.S. Anchor Mfg., Inc. v. Rule Indus., Inc., 7 F.3d 986, 993 (11th Cir.1993) (eviden-tiary rulings); Church of Scientology Flag Serv., Org. v. City of Clearwater, 2 F.3d 1509, 1513 (11th Cir.1993) (attorneys’ fees). III. THE CONSENT DECREE MODIFICATION ISSUES A. CONSENT DECREE MODIFICATION LAW The Supreme Court has articulated a two-pronged approach to determining when, and to what extent, an institutional-reform consent decree that “arguably relates to the vindication of a constitutional right” should be modified. Rufo v. Inmates of Suffolk County Jail, — U.S. -, - n. 7, 112 S.Ct. 748, 760 n. 7, 116 L.Ed.2d 867 (1992). The first prong requires the party seeking modification to “establish that a significant change in facts or law warrants revision of the decree.” Id. at-, 112 S.Ct. at 765. If the moving party satisfies this requirement, then the second prong requires the court to make modifications that are “suitably tailored” to address the new factual or legal environment. Id. We now elaborate on this dual inquiry. 1. Rufo’s First Prong: Prerequisites for Modification Rufo normally permits modification of a consent decree only to accommodate new factual or legal circumstances. The sorts of factual changes that may qualify include unanticipated developments that render continuation of the decree “inequitable,” Jacksonville Branch, NAACP v. Duval County Sch. Bd., 978 F.2d 1574, 1582 (11th Cir.1992), or that, “for reasons unrelated to past discrimination or to the fault of the parties,” make it extremely difficult or impossible to satisfy obligations that, while imposed by the decree, are not part of its fundamental purpose, United States v. City of Miami, 2 F.3d 1497, 1509 (11th Cir.1993). However, a district court should not modify “long-standing goals in consent decrees merely because the goals have not been achieved.” Id. at 1509. Rufo similarly provides for flexibility in the face of changing legal standards, but does not mandate modifications in response to every legal development. For example, a court need not necessarily “rewrite a consent decree so that it conforms to the constitutional floor” just because that floor drops after entry of the decree. Rufo, — U.S. at -, 112 S.Ct. at 764. On the other hand, a rising constitutional floor — or, as in this case, a falling constitutional ceiling — may make modifications necessary. Above all, “[a] consent decree must ... be modified if ... one or more of the obligations placed upon the parties has become impermissible under federal law,” id. at -, 112 S.Ct. at 762, and that is the aspect of Rufo with which we grapple in the present ease. 2. Rufo’s Second Prong: Suitably Tailored Modifications Once a court has determined that some modification is warranted because of a significant change in law or fact, the second prong of the Rufo analysis comes into play. This prong requires the court to determine the appropriate scope of the changes, accepting only proposals that are “suitably tailored” to address significant factual developments or conflicts between new legal standards and the requirements of the decree. Rufo, — U.S. at -, 112 S.Ct. at 765. This determination requires a flexible “exercise of that court’s equitable power,” City of Miami, 2 F.3d at 1509, but the district court’s discretion is not unlimited. The court may not modify a decree in a way that would “violate the basic purpose of the decree,” and must under no circumstances “create or perpetuate a constitutional violation.” Rufo, — U.S. at - - -, 112 S.Ct. at 762-63. We now turn to the question of whether the district court properly exercised its equitable discretion when it rejected some of the appellants’ proposed modifications. This inquiry will require us to decide whether the court modified the consent decrees’ race- and gender-based remedies sufficiently to make them permissible under current constitutional standards. Because racial and gender classifications attract different levels of scrutiny under the Equal Protection Clause, we analyze separately the decrees’ race- and gender-conscious provisions. B. MODIFICATION OF THE RACE-CONSCIOUS AFFIRMATIVE ACTION' PROVISIONS IN THIS CASE 1. Rufo’s First Prong: Prerequisites for Modification The district court approved the City and Board decrees in 1981, thirteen years ago. The Supreme Court had, at that time, just begun to address the constitutionality of affirmative action. See Fullilove v. Klutznick, 448 U.S. 448, 100 S.Ct. 2758, 65 L.Ed.2d 902 (1980); Regents of Univ. of Cal. v. Bakke, 438 U.S. 265, 98 S.Ct. 2733, 57 L.Ed.2d 750 (1978); Califano v. Webster, 430 U.S. 313, 97 S.Ct. 1192, 51 L.Ed.2d 360 (1977). Since then, the Court has repeatedly revisited this issue, substantially changing affirmative action jurisprudence. Most significantly, City of Richmond v. J.A. Croson Co., 488 U.S. 469, 498-508, 109 S.Ct. 706, 724-30, 102 L.Ed.2d 854 (1989), established that voluntary, race-conscious, local-government affirmative action programs are subject to strict scrutiny. Prior to Croson, “a majority of the Supreme Court had never joined in one opinion on the constitutionality” of such programs. Peightal v. Metropolitan Dade County, 940 F.2d 1394, 1398-99 (11th Cir.1991) (footnote omitted), cert. denied, — U.S. -, 112 S.Ct. 969, 117 L.Ed.2d 134 (1992). Croson sufficiently altered the legal landscape to warrant modifications to the present decrees under Rufo. As we discuss later in this opinion, Croson has rendered parts of the decrees unconstitutional. 2. Rufo’s Second Prong: Suitably Tailored Modifications Rufo’s second prong requires that consent decrees be modified to avoid any violations of governing constitutional standards. The relevant constitutional standard in this case is Croson’s strict scrutiny test. While it is true that Croson applies only to voluntary affirmative action programs, see Croson, 488 U.S. at 491-93, 109 S.Ct. at 720-21, we have previously held that, because of their peculiar procedural history, the present decrees should be treated as “a voluntary affirmative action plan for purposes of equal protection analysis.” In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d 1492, 1501 n. 23 (11th Cir.1987), aff'd sub nom., Martin v. Wilks, 490 U.S. 755, 109 S.Ct. 2180, 104 L.Ed.2d 835 (1989). Under strict scrutiny, an affirmative action plan must be based upon a “compelling governmental interest” and must be “narrowly tailored” to achieve that interest. S.J. Groves & Sons Co. v. Fulton County, 920 F.2d 752, 767 (11th Cir.), cert. denied, 500 U.S. 959, 111 S.Ct. 2274, 114 L.Ed.2d 725, and cert. denied, 501 U.S. 1252, 111 S.Ct. 2893, 115 L.Ed.2d 1057 (1991); see also Croson, 488 U.S. at 498-508, 109 S.Ct. at 724-30. We address separately those two requirements as they apply to this decree. a. Croson’s Compelling Government Interest Requirement Strict scrutiny’s compelling government interest requirement was designed “to ‘smoke out’ illegitimate uses of race by assuring that the legislative body is pursuing a goal important enough to warrant use of a highly suspect tool.” Croson, 488 U.S. at 493, 109 S.Ct. at 721 (plurality opinion of O’Connor, J.). In practice, the interest that is alleged in support of racial preferences is almost always the same — remedying past or present discrimination. United States v. City of San Francisco, 696 F.Supp. 1287, 1301 (N.D.Cal.1988), aff'd in part and modified in part on other grounds sub nom. Davis v. City of San Francisco, 890 F.2d 1438 (9th Cir.1989), cert. denied, 498 U.S. 897, 111 S.Ct. 248, 112 L.Ed.2d 206 (1990). That interest is widely accepted as compelling. See, e.g., Wygant v. Jackson Bd. of Educ., 476 U.S. 267, 286, 106 S.Ct. 1842, 1853, 90 L.Ed.2d 260 (1986) (O’Connor, J., concurring); Cone Corp. v. Hillsborough County, 908 F.2d 908, 916 (11th Cir.), cert. denied, 498 U.S. 983, 111 S.Ct. 516, 112 L.Ed.2d 528 (1990); Howard v. McLucas, 871 F.2d 1000, 1006-08 (11th Cir.), cert. denied, 493 U.S. 1002, 110 S.Ct. 560, 107 L.Ed.2d 555 (1989). As a result, the true test of an affirmative action program is usually not the nature of the government’s interest, but rather “the adequacy of the evidence of discrimination” offered to show that interest. City of San Francisco, 696 F.Supp. at 1301. Without an adequate showing of discrimination, the government’s assertion that affirmative action is necessary lacks credibility. See Croson, 488 U.S. at 505, 109 S.Ct. at 728. Therefore, when a consent decree providing race-conscious relief is challenged as unconstitutional, the district court must make a factual determination that the public employer has “ ‘a strong basis in evidence for its conclusion that’ ” racial discrimination necessitates affirmative action. Howard, 871 F.2d at 1007 (quoting Wygant, 476 U.S. at 277, 106 S.Ct. at 1849). Certain aspects of this inquiry are well established. A local-government employer cannot rest on an “amorphous claim” of societal discrimination, Croson, 488 U.S. at 499, 109 S.Ct. at 724, on “simple legislative assurances of good intention,” id. at 500, 109 S.Ct. at 725, or on congressional findings of discrimination in the national economy, id. at 504, 109 S.Ct. at 727. Public employers may, however, justify affirmative action by demonstrating “gross statistical disparities” between the proportion of minorities hired by the public employer and the proportion of minorities willing and able to do the work. Id. at 501, 109 S.Ct. at 725 (internal quotation marks omitted); see also Cone Corp., 908 F.2d at 916 (finding a prima facie case of discrimination sufficient to justify race-conscious relief where minorities owned 12% of the contracting businesses but received only 1.2% of the local government’s contracting dollars); Howard, 871 F.2d at 1007 (upholding a finding of discrimination based on statistical evidence, including the fact that black employees spent an average of three times longer than white employees in low-grade wage jobs). Anecdotal evidence may also be used to document discrimination, especially if buttressed by relevant statistical evidence. Cone Corp., 908 F.2d at 916. Although Croson requires that a public employer show strong evidence of discrimination when defending an affirmative action plan, the Supreme Court has never required that, before implementing affirmative action, the employer must have already proved that it has discriminated. On the contrary, formal findings of discrimination need neither precede nor accompany the adoption of affirmative action. Wygant, 476 U.S. at 286, 106 S.Ct. at 1853 (O’Connor, J., concurring) (rejecting any formal findings requirement); id. at 305, 106 S.Ct. at 1863 (Marshall, J., dissenting, joined by Brennan and Blackmun, JJ.) (stating that “[t]he Court is correct to recognize, as it does at least implicitly today, that formal findings of past discrimination are not a necessary predicate to the adoption of affirmative-action policies”); id. at 313, 106 S.Ct. at 1867 (Stevens, J., dissenting) (arguing that a showing of past discrimination is not necessary to finding a compelling interest in racial classifications with purely prospective effect); Howard, 871 F.2d at 1007 (specifically rejecting the intervenor white employees’ argument “that a showing of past discrimination must precede the implementation of the promotional relief and that this showing may be made only through the employer’s own admittance of such discrimination or through a judicial finding of past discrimination”); cf. Contractors Ass’n v. City of Philadelphia, 6 F.3d 990, 1004 (3d Cir.1993) (noting that federal courts have admitted evidence that supports affirmative action, even when that evidence was developed after the affirmative action plan); Harrison & Burrowes Bridge Constructors, Inc. v. Cuomo, 981 F.2d 50, 60 (2d Cir.1992) (“The law is plain that the constitutional sufficiency of a state’s proffered reasons necessitating an affirmative action plan should be assessed on whatever evidence is presented, whether prior to or subsequent to the program’s enactment.”). This is because, as Justice O’Connor has explained A violation of federal statutory or constitutional requirements does not arise with the making of a finding; it arises when the wrong is committed. Contemporaneous findings serve solely as a means by which it can be made absolutely certain that the governmental actor truly is attempting to remedy its own unlawful conduct when it adopts an affirmative action plan .... Such findings, when voluntarily made by a public employer, obviously are desirable in that they provide evidentiary safeguards .... If contemporaneous findings were required of public employers in every case as a precondition to the constitutional validity of their affirmative action efforts, however, the relative value of these eviden-tiary advantages would diminish, for they could be secured only by the sacrifice of other vitally important values. The imposition of a requirement that public employers make findings that they have engaged in illegal discrimination before they engage in affirmative action programs would severely undermine public employers’ incentive to meet voluntarily their civil rights obligations.... ... [P]ublic employers are trapped between the competing hazards of liability to minorities if affirmative action is not taken to remedy apparent employment discrimination and liability to nonminorities if affirmative action is taken. Where these employers, who are presumably fully aware both of their duty under federal law to respect the rights of all their employees and of their potential liability for failing to do so, act on the basis of information which gives them a sufficient basis for concluding that remedial action is necessary, a contemporaneous findings requirement should not be necessary. Wygant, 476 U.S. at 289-91, 106 S.Ct. at 1855-56 (O’Connor, J., concurring). For these and related reasons, the Supreme Court has required a public employer defending an affirmative action plan to show only that it has “a ‘strong basis in evidence for its conclusion that remedial action was necessary.’” Croson, 488 U.S. at 500, 109 S.Ct. at 725 (quoting Wygant, 476 U.S. at 277, 106 S.Ct. at 1849 (plurality opinion)). At the time the City and the Board accepted the present consent decrees, they already had a “strong basis in evidence” for concluding that race-based relief was needed to correct discrimination in the police and fire departments. When it approved the consent decrees, the district court noted that the City and the Board had good reason to believe that they had discriminated in those two departments. United States v. Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) 1834, 1838, 1981 WL 27018 (N.D.Ala.1981), aff'd, 720 F.2d 1511 (11th Cir.1983). The district court evaluated an extensive record that supported this conclusion. Most importantly, the district court stated: This court at the first trial found — and the Fifth Circuit agreed — that blacks applying for jobs as police officers and firefighters were discriminated against by the tests used by the Personnel Board to screen and rank applicants. The evidence presented at the second trial established, at the .01 level of statistical significance, that blacks were adversely affected by the exam used by the Personnel Board to screen and rank applicants for the position of police se