Skip to content

Instantly share code, notes, and snippets.

@jameshi16
Created January 25, 2022 04:30
Show Gist options
  • Save jameshi16/bf6583a09a05d490c6ad36d68d377105 to your computer and use it in GitHub Desktop.
Save jameshi16/bf6583a09a05d490c6ad36d68d377105 to your computer and use it in GitHub Desktop.
[Mine] Duty Planning on Google Sheets with LP
/**
* 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());
}
/**
* 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);
}
// 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;
/**
* 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);
}
}
}
}
}
/**
* 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());
}
}
@shiva-karthick
Copy link

Nice work!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment