[Mine] Duty Planning on Google Sheets with LP

Buttons.gs

/**
 * Ensures that the dates are laid out in the grid correctly.
 */
function setup() {
  SpreadsheetApp.getActive().toast("Setting up...");

  const days = Math.floor((highestDate - lowestDate) / (1000 * 60 * 60 * 24));
  for (var i = 1; i < days + 2; i++) {
    daysRange.getCell(1, i).setValue(i);
  }
}

/**
 * Clears the availability within the generation range
 */
function clearAvailability() {
  SpreadsheetApp.getActive().toast("Clearing availability...", "Clearing...", 60);
  const fromDateRaw = new Date(genDateRange.getCell(1, 1).getValue());
  const toDateRaw = new Date(genDateRange.getCell(2, 1).getValue());
  const fromDate = (fromDateRaw - lowestDate) / (1000 * 60 * 60 * 24);
  const toDate = (toDateRaw - lowestDate) / (1000 * 60 * 60 * 24);
  
  grid.getRange(3, 3 + fromDate, grid.getRange('C3:C').getNumRows(), toDate + 1).setValue("");
}

/**
 * Gets the raw amount of personnel
 * @returns {Number}
 */
function getRawPersonalCount() {
  return grid.getRange("A3:A").getValues().reduce((prev, curr) => curr.toString().trim() != "" ? prev + 1 : prev, 0);
}

/**
 * Updates the availability from the final input sheet to the grid from the generation settings range
 */
function updateAvailability() {
  SpreadsheetApp.getActive().toast("Updating unavailability...", "Updating...", 60);

  const prevSheet = SpreadsheetApp.getActiveSheet();
  SpreadsheetApp.setActiveSheet(grid);

  const rowCount = getRawPersonalCount();
  const colCount = getConsideredDaysCount();
  const availType = availSheet.getRange("C2:C").getValues();
  const formIdRange = availSheet.getRange("B2:B").getValues();
  const dateFromRange = availSheet.getRange("D2:D").getValues();
  const dateToRange = availSheet.getRange("E2:E").getValues();
  const fids = grid.getRange(3, 1, rowCount, 1).getValues();
  const pTags = rawPersList.getRange("E2:E").getValues();
  const dTags = grid.getRange("C2:2").getValues();

  const sumMatrix = grid.getRange(3, 3, rowCount, colCount);
  const sumMatrixValues = sumMatrix.getValues();

  for (var i = 0; i < dateFromRange.length; i++) {
    const dateFrom = dateFromRange[i][0];
    const dateTo = dateToRange[i][0];
    const availT = availType[i][0];
    const formID = formIdRange[i][0];

    if (dateFrom == "") break; // due to the way the spreadsheet is configured, empty string means EOF
    const offset = Math.floor((dateFrom - lowestDate) / (1000 * 60 * 60 * 24));
    const offsetTo = Math.floor((dateTo - lowestDate) / (1000 * 60 * 60 * 24));
    const duration = offsetTo - offset;

    if (offset < 0) {
      continue; // out of range of consideration
    }

    var rowIndex = null;
    for (var k = 0; k < fids.length; k++) {
      if (fids[k][0] == formID) {
        rowIndex = k;
      }
    }

    if (rowIndex == null) continue;
    
    for (var j = 0; j < duration + 1; j++) {
      if (availT == "Unavailable") {;
        sumMatrixValues[rowIndex][offset + j] = "L";
      }
    }
  }

  // handle CMI dates (Chinese New Year, Hari Raya Puasa, Deepavali)
  for (var dTi = 0; dTi < dTags[0].length; dTi++) {
    const dTagsList = dTags[0][dTi].toString().split(",");
    for (var dTagsI = 0; dTagsI < dTagsList.length; dTagsI++) {
      if (dTagsList[dTagsI] != "C" && dTagsList[dTagsI] != "M" && dTagsList[dTagsI] != "I") continue;

      for (var pTi = 0; pTi < pTags.length; pTi++) {
        const pTagsList = pTags[pTi].toString().split(",");

        for (var pTagsI = 0; pTagsI < pTagsList.length; pTagsI++) {
          if (pTagsList[pTagsI] == dTagsList[dTagsI] && sumMatrixValues[pTi][dTi] != "L") {
            sumMatrixValues[pTi][dTi] = "C";
          }
        }
      }
    }
  }
  
  sumMatrix.setValues(sumMatrixValues);

  SpreadsheetApp.setActiveSheet(prevSheet);
}

/**
 * The "Update Availability" button from "[H] Generation Settings"
 */
function btnUpdateAvailability() {
  setup();
  clearAvailability();
  updateAvailability();
  SpreadsheetApp.getActive().toast("Done", "Done", 5);
}

/**
 * The "Generate" button from "[H] Generation Settings"
 */
function btnGenerate() {
  glos();
  updatedDateCell.setValue(new Date());
}

Events.gs

/**
 * If the manual input sheet is updated, automatically timestamp.
 * @param {SpreadsheetApp.Sheet} sheet
 * @param {SpreadsheetApp.Range} range
 */
function onInputSheetIDEdit(sheet, range) {
  if (range.isBlank()) return;

  for (var i = 1; i < range.getNumRows() + 1; i++) {
    var cell =  sheet.getRange("A" + (range.getRowIndex() + i - 1));
    cell.setValue(new Date());
  }
}

function onEdit(e) {
  /** @type {SpreadsheetApp.Sheet} */
  var sheet = e.source.getActiveSheet();
  if (sheet.getSheetName() == MANUAL_INPUT_SHEET_NAME) onInputSheetIDEdit(sheet, e.range);
}

Globals.gs

// Sheets, Lists
const genSheet      = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("[H] Generation Settings");
const grid          = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("[H] Grid");
const sumGrid       = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("[M] Summary (Grid)");
const availSheet    = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("[M] Confirmed Inputs");
const personnelList = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("[M] Final Personnel List");
const rawPersList   = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("[H] Personnel List");

// Ranges
const genDateRange  = genSheet.getRange("B2:B3");
const conDateRange  = genSheet.getRange("B6:B7");
const daysRange     = grid.getRange("C1:1");

// Cells
const updatedDateCell = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("[M] Summary (List)").getRange("B1");

// Lowest & Highest dates considered
const lowestDate = (new Date(genDateRange.getCell(1, 1).getValue())) < (new Date(conDateRange.getCell(1, 1).getValue())) ? new Date(genDateRange.getCell(1, 1).getValue()) : new Date (conDateRange.getCell(1, 1).getValue());
const highestDate = (new Date(genDateRange.getCell(2, 1).getValue())) > (new Date(conDateRange.getCell(2, 1).getValue())) ? new Date(genDateRange.getCell(2, 1).getValue()) : new Date (conDateRange.getCell(2, 1).getValue());

// Constants
const MANUAL_INPUT_SHEET_NAME = "[H] Manual Input";

const NORMAL_POINTS         = genSheet.getRange("B10").getValue();
const WEEKENDS_POINTS       = genSheet.getRange("B11").getValue();
const PUBLIC_HOLIDAY_POINTS = genSheet.getRange("B12").getValue();

const PREFERRED_DATE_SCORE    = 2;
const NORMAL_DATE_SCORE       = 1;
const UNAVAILABLE_DATE_SCORE  = 0;

const BLACKOUT_DAYS_AFTER_DUTY = 7;

const POINTS_DIFFERENCE_FACTOR = 1.2;

GLOS.gs

/**
 * Gets the number of personnel to be considered in the calculation
 * @returns {Number}
 */
function getActivePersonnelCount() {
  const activeFIs = personnelList.getRange("A2:A").getValues();
  var count = 0;
  for (var i = 0; i < activeFIs.length; i++) {
    if (activeFIs[i] == "") break;
    count++;
  }
  return count;
}

/**
 * Gets the number of days to be considered in the calculation
 * @returns {Number}
 */
function getConsideredDaysCount() {
  return Math.floor((highestDate - lowestDate) / (1000 * 60 * 60 * 24)) + 1;
}

/**
 * Gets the days that can be modified by the model in the calculation
 * @returns {Number}
 */
function getCalculationDaysCount() {
  const startDate = new Date(genDateRange.getCell(1, 1).getValue());
  const endDate = new Date(genDateRange.getCell(2, 1).getValue());

  return Math.floor((endDate - startDate) / (1000 * 60 * 60 * 24)) + 1;
}

/**
 * Gets the preferred dates, expressed by a matrix adjustment
 * @returns {Number[][]}
 */
function getPreferredDateMatrix() {
    const availType = availSheet.getRange("C2:C").getValues();
    const formIdRange = availSheet.getRange("B2:B").getValues();
    const dateFromRange = availSheet.getRange("D2:D").getValues();
    const dateToRange = availSheet.getRange("E2:E").getValues();
    const numRows = getActivePersonnelCount();
    const numCols = getConsideredDaysCount();
    const fids = personnelList.getRange('A2:A').getValues();
    var preferredDates = Array.from(Array(numRows), () => new Array(numCols).fill(0));

    for (var i = 0; i < dateFromRange.length; i++) {
      const dateFrom = dateFromRange[i][0];
      const dateTo = dateToRange[i][0];
      const availT = availType[i][0];
      const formID = formIdRange[i][0];

      if (dateFrom == "") break; // due to the way the spreadsheet is configured, empty string means EOF
      var rowIndex = null;
      for (var k = 0; k < fids.length; k++) {
        if (fids[k][0] == formID) {
          rowIndex = k;
        }
      }

      if (rowIndex == null) continue;

      const offset = Math.floor((dateFrom - lowestDate) / (1000 * 60 * 60 * 24));
      const offsetTo = Math.floor((dateTo - lowestDate) / (1000 * 60 * 60 * 24));
      const duration = offsetTo - offset;

      if (offset < 0) {
        continue; // out of range of consideration
      }
      
      for (var j = 0; j < duration + 1; j++) {
        if (availT == "Preferred") {
          preferredDates[rowIndex][offset + j] = 1;
        }
      }
    }

    return preferredDates;
}

/**
 * Calculates the score adjustment matrix.
 * @returns {Number[][]}
 */
function getScoreAdjustmentMatrix() {
  const numRows = getActivePersonnelCount();
  const numCols = getConsideredDaysCount();

  var scoreAdjustmentMatrix = Array.from(Array(numRows), () => new Array(numCols).fill(NORMAL_DATE_SCORE));
  
  // Leaves, Considerations
  const workingMatrix = sumGrid.getRange("C3:CQ").getValues();
  for (var wmi = 0; wmi < workingMatrix.length; wmi++) {
    for (var wmj = 0; wmj < workingMatrix[wmi].length; wmj++) {
      if (workingMatrix[wmi][wmj] == "C" || workingMatrix[wmi][wmj] == "L") {
        scoreAdjustmentMatrix[wmi][wmj] = UNAVAILABLE_DATE_SCORE;
      }
    }
  }

  // Preferred dates
  const preferredDateMatrix = getPreferredDateMatrix();
  for (var pdmi = 0; pdmi < preferredDateMatrix.length; pdmi++) {
    for (var pdmj = 0; pdmj < preferredDateMatrix[pdmi].length; pdmj++) {
      if (preferredDateMatrix[pdmi][pdmj] == 1) {
        scoreAdjustmentMatrix[pdmi][pdmj] = PREFERRED_DATE_SCORE;
      }
    }
  }

  return scoreAdjustmentMatrix;
}

/**
 * Gets the matrix that represents cells that should not be touched.
 * @returns {Number[][]} If there is a value (0 - No duty, 1 - Duty, B - Backup), then the duty has been set in stone.
 */
function getSetInStoneMatrix() {
  const numRows = getActivePersonnelCount();
  const numCols = getConsideredDaysCount();

  var stoneMatrix = Array.from(Array(numRows), () => new Array(numCols).fill(-1));

  const workingMatrix = sumGrid.getRange("C3:CQ").getValues();
  for (var wmi = 0; wmi < stoneMatrix.length; wmi++) {
    for (var wmj = 0; wmj < stoneMatrix[wmi].length; wmj++) {
      if (workingMatrix[wmi][wmj] == "1" || workingMatrix[wmi][wmj] == "0") {
        stoneMatrix[wmi][wmj] = parseInt(workingMatrix[wmi][wmj]);
      } else if (workingMatrix[wmi][wmj] == "B") {
        stoneMatrix[wmi][wmj] = 2;
      }
    }
  }

  return stoneMatrix;
}

/**
 * Calculates the points for performing duty on each day.
 * @returns {Number[][]}
 */
function calculateDutyPointsArray() {
  const taggedDays = grid.getRange("C2:2").getValues();
  var points = new Array(getConsideredDaysCount());

  for (i = 0; i < points.length; i++) {
    if (taggedDays[0][i].toString().split(",").reduce((prev, curr) => (prev || curr == "W") ? true : false, false)) {
      points[i] = WEEKENDS_POINTS;
    } else if (taggedDays[0][i].toString().split(",").reduce((prev, curr) => (prev || curr == "P") ? true : false, false)) {
      points[i] = PUBLIC_HOLIDAY_POINTS;
    } else points[i] = NORMAL_POINTS;
  }

  return points;
}

/**
 * Calculates the number of normal working days
 * @param {Number[]} dPointsArray 
 * @returns {Number}
 */
function numberOfNormalDays(dPointsArray) {
  var count = 0;
  for (var i = 0; i < dPointsArray.length; i++) {
    if (dPointsArray == 1) count++;
  }
  return count;
}

function glos() {
  SpreadsheetApp.getActiveSpreadsheet().toast("Pre-requisite calculations...", "Calculating", 10);
  const engine = LinearOptimizationService.createEngine();

  const numRows = getActivePersonnelCount();
  const numCols = getConsideredDaysCount();
  var dutyMatrix = Array.from(Array(numRows), () => new Array(numCols));
  var scoreAdjustmentMatrix = getScoreAdjustmentMatrix();
  var setInStoneMatrix = getSetInStoneMatrix();

  const dutyPointsArray = calculateDutyPointsArray();
  const pointAdjustmentArray = personnelList.getRange("C2:C").getValues();

  const noOfWorkingDays = numberOfNormalDays(dutyPointsArray[0]);
  const minWkdayPerPerson = Math.floor(noOfWorkingDays / numRows);
  const minDutyPerPerson = Math.floor(numCols / numRows);
  const potentialPoints = (dutyPointsArray.reduce((p, c) => p + c) / numRows);

  const barrierBetweenConsideration = Math.floor((new Date(genDateRange.getCell(1, 1).getValue()) - new Date(conDateRange.getCell(1, 1).getValue())) / (1000 * 60 * 60 * 24));

  SpreadsheetApp.getActiveSpreadsheet().toast("Building model...", "Calculating", 30);
  // inputs (binary variable, dutyMatrix & backup. Both should have same size)
  for (i = 1; i < numRows + 1; i++) {
    for (j = 1; j < numCols + 1; j++) {
      engine.addVariable('slot_' + i + '_' + j, 0, 1, LinearOptimizationService.VariableType.INTEGER);
      engine.addVariable('backup_' + i + '_' + j, 0, 1, LinearOptimizationService.VariableType.INTEGER);
    }
  }
  engine.addVariable('points_difference_threshold', 0, 10, LinearOptimizationService.VariableType.CONTINUOUS);

  // constriant: set in stone & minimum personnel
  for (i = 0; i < numRows; i++) {
    for (j = 0; j < numCols; j++) {
      if (setInStoneMatrix[i][j] != -1) { // found in stone matrix
        if (setInStoneMatrix[i][j] < 2) {
          var constraint = engine.addConstraint(setInStoneMatrix[i][j], setInStoneMatrix[i][j]);
          var backupConstraint = engine.addConstraint(0, 0);

          constraint.setCoefficient('slot_' + (i + 1) + '_' + (j + 1), 1);
          backupConstraint.setCoefficient('backup_' + (i + 1) + '_' + (j + 1), 1);
        } else {
          var constraint = engine.addConstraint(0, 0);
          var backupConstraint = engine.addConstraint(1, 1);

          constraint.setCoefficient('slot_' + (i + 1) + '_' + (j + 1), 1);
          backupConstraint.setCoefficient('backup_' + (i + 1) + '_' + (j + 1), 1);
        }
      }
    }
  }

  // constraint: each day should only have 1 duty & 1 backup
  for (j = 1; j < numCols + 1; j++) {
    var constraint = engine.addConstraint(1, 1);
    var backupConstraint = engine.addConstraint(1, 1);
    for (i = 1; i < numRows + 1; i++) {
      constraint.setCoefficient('slot_' + i + '_' + j, 1);
      backupConstraint.setCoefficient('backup_' + i + '_' + j, 1);
    }
  }

  // constraint: no consecutive days
  for (j = 1; j < numCols; j++) {
    for (i = 1; i < numRows + 1; i++) {
      var constraint = engine.addConstraint(0, 1);
      for (k = j; k < numCols && k < j + BLACKOUT_DAYS_AFTER_DUTY + 1; k++) {
        if (k != barrierBetweenConsideration && setInStoneMatrix[i - 1][k - 1] != -1) continue;
        constraint.setCoefficient('slot_' + i + '_' + k, 1);
        constraint.setCoefficient('backup_' + i + '_' + k, 1);
      }
    }
  }

  // constraint: everyone should have around the same amount of points
  for (i = 1; i < numRows + 1; i++) {
    var lowerConstraint = engine.addConstraint(-pointAdjustmentArray[i][0] + pointAdjustmentArray[i + 1][0] + potentialPoints, 999);
    var higherConstraint = engine.addConstraint(-999, pointAdjustmentArray[i][0] - pointAdjustmentArray[i + 1][0] + potentialPoints);
    for (j = 1; j < numCols + 1; j++) {
      var point = dutyPointsArray[j - 1];
      lowerConstraint.setCoefficient('slot_' + i + '_' + j, point);
      higherConstraint.setCoefficient('slot_' + i + '_' + j, point);
    }

    lowerConstraint.setCoefficient('points_difference_threshold', 1);
    higherConstraint.setCoefficient('points_difference_threshold', -1);
  }

  // constraint: backup & actual day cannot be on leave
  for (j = 1; j < numCols + 1; j++) {
    for (i = 1; i < numRows + 1; i++) {
      if (setInStoneMatrix[i - 1][j - 1] != -1) continue;
      var point = (scoreAdjustmentMatrix[i - 1][j - 1] == 0) ? 0 : 1;
      var constraint = engine.addConstraint(0, point);
      var backupConstraint = engine.addConstraint(0, point);

      constraint.setCoefficient('slot_' + i + '_' + j, 1);
      backupConstraint.setCoefficient('backup_' + i + '_' + j, 1);
    }
  }

  // constraint: slot & backup cannot be on the same slot
  // TODO: might be redundant
  for (i = 1; i < numRows + 1; i++) {
    for (j = 1; j < numCols + 1; j++) {
      var constraint = engine.addConstraint(0, 1);
      constraint.setCoefficient('slot_' + i + '_' + j, 1);
      constraint.setCoefficient('backup_' + i + '_' + j, 1);
    }
  }

  // constraint: opportunity to earn extra should be equal
  for (i = 1; i < numRows + 1; i++) {
    var constraint = engine.addConstraint(minWkdayPerPerson, 999);
    for (j = 1; j < numCols + 1; j++) {
      if (dutyPointsArray[j] != NORMAL_POINTS) continue;
      constraint.setCoefficient('slot_' + i + '_' + j, 1);
    }
  }

  // constraint: as much as possible, everyone should be a duty & backup
  for (i = 1; i < numRows + 1; i++) {
    var constraint = engine.addConstraint(minDutyPerPerson, 999);
    var backupConstraint = engine.addConstraint(minDutyPerPerson, 999);
    for (j = 1; j < numCols + 1; j++) {
      constraint.setCoefficient('slot_' + i + '_' + j, 1);
      backupConstraint.setCoefficient('backup_' + i + '_' + j, 1);
    }
  }

  // objective: sum of points per day
  for (j = 1; j < numCols + 1; j++) {
    for (i = 1; i < numRows + 1; i++) {
      var scoreAdjustment = scoreAdjustmentMatrix[i - 1][j - 1];
      engine.setObjectiveCoefficient('slot_' + i + '_' + j, scoreAdjustment);
    }
  }
  engine.setObjectiveCoefficient('points_difference_threshold', -POINTS_DIFFERENCE_FACTOR);
  engine.setMaximization();

  // solve
  SpreadsheetApp.getActiveSpreadsheet().toast("Solving...", "Calculating", 30);
  var solution = engine.solve();
  if (!solution.isValid()) {
    Logger.log('No solution ' + solution.getStatus());
    SpreadsheetApp.getUi().alert("No solution " + solution.getStatus());
    SpreadsheetApp.getActiveSpreadsheet().toast("", "", 1);
  } else {
    Logger.log('Solution found. Status: ' + solution.getStatus());
    SpreadsheetApp.getActiveSpreadsheet().toast("Solved, points difference threshold: " +  solution.getVariableValue('points_difference_threshold') + ". Plotting values on the matrix", "Outputting", 30);
    SpreadsheetApp.setActiveSheet(sumGrid);
    const solutionMatrix = grid.getRange("C3:CQ");
    const solutionMatrixValues = solutionMatrix.getValues();
    const fids = personnelList.getRange("A2:A").getValues();
    for (i = 1; i < numRows + 1; i++) {
      const fid = fids[i - 1];
      const values = grid.getRange("A3:A").getValues();

      var rowIndex = -1;
      for (k = 0; k < values.length; k++) {
        if (values[k][0] == fid) {
          rowIndex = k;
          break;
        }
      }
      if (rowIndex == -1) continue;

      for (j = 1; j < numCols + 1; j++) {
        const duty = solution.getVariableValue('slot_' + i + '_' + j);
        const backup = solution.getVariableValue('backup_' + i + '_' + j);
        if (solutionMatrixValues[rowIndex][j - 1] == "") {
          if (duty) solutionMatrix.getCell(rowIndex + 1, j).setValue(1);
          else if (backup) solutionMatrix.getCell(rowIndex + 1, j).setValue("B");
          else solutionMatrix.getCell(rowIndex + 1, j).setValue(0);
        }
      }
    }
  }
}

Information.gs

/**
 * Run this to find out what sheet IDs you need to populate the macros
 */
function getAllSpreadsheetIds() {
  var sheets = SpreadsheetApp.getActiveSpreadsheet().getSheets();
  for (var i = 0; i < sheets.length; i++) {
    Logger.log("Sheet Name: " + sheets[i].getName() + ", Sheet ID: " + sheets[i].getSheetId());
  }
}

Nice work!