Aircraft: SR22
Phase of flight: Takeoff / Launch
Anomaly: ATC Issue All Types; Conflict Ground Conflict; Critical; Deviation / Discrepancy - Procedural Clearance; Ground Incursion Runway

This [occurred during a very busy period]. A controller retired; and the facility is unable to adequately staff the tower. Due to this fact we are now on mandatory 6 day work weeks. I started my day and took over the schedule. I was left with two CICs (including myself); and two Certified Professional Controllers (CPCs); and they all needed to go on lunch break. I took position; started rotating people; and was working traffic. I worked for two hours and then took about a 15 minute break and came back to relieve the other CIC who was about to go over 2 hours. On this second session is when the incident happened:XA:01 Tug #1 with an aircraft in tow called Ground to reposition (would require crossing [the Runway]). Ground pulled him up to the runway.XA:03 GC coordinated with LC to cross runway after departing aircraft.XA:03 Departing aircraft airborne. -GC crossed runway after aircraft departed.XA:05 LC cleared Aircraft X for takeoff; overlooked runway crossing.XA:07 Aircraft X radar contact.Aircraft X was airborne before [taxiway intersection] at approximately 600 feet and was given an early left cross wind departure; Tug #1 had almost finished crossing the runway; but was still partly on the active. Approximately 2;245 feet of separation was maintained; but the Airport Surface separation was lost.I was trying to balance the schedule; the traffic volume; the skeleton crew; and had an oversight. Recommendation would be a faster process to get staffing. Traffic started to pick up early morning and continued throughout the day peaking later [in the evening]. The facility recently became understaffed when two controllers were released to two other facilities three weeks before and an unexpected departure from a controller who retired. The Tower was understaffed which subsequently lead everyone to 6 day work weeks. The incident occurred on my last day of the 6 day work week and an hour before I was scheduled to leave. I was working Flight Data; Clearance Delivery; and Ground Control. Tugs from the two FBOs on the field were crossing the runway back and forth all day to overflow parking.A Tug called me with an aircraft in tow and requested to cross the runway at an intersection. I instructed the tow to hold short of the runway. I coordinated with local cross runway at [taxiway intersection] behind the departing aircraft (I scanned the runway and looked at the arrivals and determined that we had adequate time to get a crossing.) Shortly after coordinating the cross the aircraft became airborne. Once the aircraft became airborne and passed the intersection I cleared the Tug to cross the runway at the taxiway. As the crossing started I began reading a clearance and listening to read back from an aircraft while viewing the crossing. While reading the clearance unbeknownst to me Local clears Aircraft X for takeoff. As I'm about to tell Local crossing complete I see the Aircraft X flying overhead about 900 feet turning southbound on a left crosswind departure. The tail of the aircraft being towed was still on the runway. I immediately asked Local if he cleared the Aircraft X for takeoff referencing the crossing and Local realizing what occurred advised me in fact that they did clear Aircraft X for takeoff and forgot about the crossing we had coordinated.I believe that a standalone CIC should be put in place when it is busy and it should not be combined with local as it was; as well I could have and will now always never read a clearance or listen to a read back when a crossing is in progress. The event is my fault as much as it was the local controllers for not being a good tower team member and scanning the full runway for a second time; if so I could have caught Aircraft X. Triple checking the runway during crossings will now be a routine of mine from now on. Lastly adequate staffing would have greatly improved the safety of the operation. Local Controller allowed the Ground Controller to approve a tug towing an aircraft to cross the active runway. The Local Controller forgot about the tug crossing the runway and cleared an aircraft for takeoff. The tug towing the aircraft had not cleared the runway when the departing aircraft took off.