How much faster are arrays than accessing Google Sheets cells within Google Scripts?

The impact magnitude will depend on how much reading and writing you are doing. If a lot of incremental data transfer is currently used, then changing your approach can yield massive benefit.

Calls to the Spreadsheet API generally take 0.01 seconds or more to complete. Calls that import / export data, or call sub-functions, will take longer (e.g. getDataRange, getValue(s), setValue(s)). Apps Script is smart enough to optimize some successive calls, but if you are alternating reads and writes, then nothing on Google’s end can help you.
You can view this timing data on the View -> Execution Transcript menu.

My suggestion is to move any existing cell-based validation formulas into script functions that operate on a passed employee name, an object mapping between employees and the shifts they have already “worked”, and the proposed shift to work. Then you’d be able to use 1 call to import the employee – day availability list, and for each day, for each shift, validate that a randomly chosen available employee can work it, given their previous shifts in the scheduling period. Lastly, you’d write your object back to the sheet(s).

---

Timing Script (which gets internally optimized by google due to successive reads)

function writeRand_(rows, cols)
{
  var datasheet = SpreadsheetApp.openById(ssid).getSheetByName('Sheet1');
  datasheet.getDataRange().clearContent();
  var rand = [];
  for(var row = 0; row < rows; ++row)
  {
    var data = [];
    for(var col = 0; col < cols; ++col)
      data.push(Math.random());
    rand.push(data);
  }
  datasheet.getRange(1, 1, rand.length, rand[0].length).setValues(rand);
  return datasheet;
}

function readAndTime()
{
  var rows = 50, cols = 8;
  var datasheet = writeRand_(rows, cols);
  // sum one-by-one
  var sum1 = 0;
  var startRangeSum = new Date().getTime();
  for(var row = 1; row <= rows; ++row)
    for(var col = 1; col <= cols; ++col)
      sum1 += datasheet.getRange(row, col).getValue()-0;
  var endRangeSum = new Date().getTime();
  // Read all, then sum.
  var sum2 = 0;
  var startArraySum = new Date().getTime();
  var inputs = datasheet.getDataRange().getValues();
  for(var row = 0; row < inputs.length; ++row)
    for(var col = 0; col < inputs[0].length; ++col)
      sum2 += inputs[row][col]-0;
  var endArraySum = new Date().getTime();
  Logger.log("Value count: " + rows * cols);
  Logger.log("Range sum: " + (endRangeSum - startRangeSum)/1000 + " sec. " + sum1);
  Logger.log("Array sum: " + (endArraySum - startArraySum)/1000 + " sec. " + sum2);
}

The above gives me ~.8s for range and .2s for array – and that .2s is essentially all due to the time it takes to call getDataRange() to make inputs