faarabi / scheduling-network-data

Gurobi model and heuristic algorithms to solve scheduling jobs with degradation rate.

Description

This research considers scheduling spatially distributed jobs with degradation. A mixed integer programming (MIP) model is developed for the linear degradation case in which no new jobs arrive. Properties of the model are analyzed, following which three heuristics are developed, enhanced greedy, chronological decomposition and simulated annealing. Numerical tests are conducted to: (i) establish limits of the exact MIP solution, (ii) identify the best heuristic based on an analysis of performance on small problem instances for which exact solutions are known, (iii) solve large problem instances and obtain lower bounds to establish solution quality, and (iv) study the effect of three key model parameters. Findings from our computational experiments indicate that: (i) exact solutions are limited to instances with less than 14 jobs; (ii) the enhanced greedy heuristic followed by the application of the simulated annealing heuristic yields high quality solutions for large problem instances in reasonable computation time; and (iii) the factors “degradation rate” and “work hours” have a significant effect on the objective function. To demonstrate applicability of the model, a case study is presented based on a pothole repair scenario from Buffalo, New York, USA. Findings from the case study indicate that scheduling spatially dispersed jobs with degradation such as potholes requires: (i) careful consideration of the number of servers assigned, degradation rate and depot location; (ii) appropriate modeling of continuously arriving jobs; and (iii) appropriate incorporation of equity consideration. For more details about the results or acces to the full article please see Paper1.pdf or link: https://www.sciencedirect.com/science/article/abs/pii/S0038012119304719

Files

1. GitHubData.txt contains a simulated data set for a network of jobs with degradation rate. This data set includes the cordinates of 200 jobs and the fixed processing time and degradation rate related to each job. To find the distance between any two specific jobs, we have made a network of nodes (each job is a node) and found the distances between any two of them by using euclidean distances.

2. Paper1.pdf is the file of related paper which is published in socio-economic journal.