According to Wikipedia, FreeBSD jails were available in a release version in 2000. Linux had Virtuozzo in 2001, explicitly for the use case we would call VPS today. Solaris didn't have zones until 2005.