JUST-IN-TIME SCHEDULING PROBLEMS ON IDENTICAL PARALLEL MACHINES

Problems involving Just-In-Time (JIT) scheduling provide an interesting and difficult challenge, which is addressed critically within this paper. This study considers the scheduling of parallelidentical machines to maximize the (weighted) number of on-time jobs. This problem is known to be NP-complete. Three problems were dealt with in this paper. Two greedy heuristics with time complexity O(n log n) are provided for maximizing the weighted number of on-time jobs with equal processing times. Two greedy heuristic algorithms are proposed for solving the unweighted number of on-time jobs on m parallel identical machines using two different approaches. It is shown by computational and worst-case analysis that these algorithms with time complexity O(nm+1 log n) will give results very close to the optimal solutions. Lastly, an optimal greedy heuristic solution is provided for solving the problem of maximizing the number of on-time agreeable jobs with equal processing time with a running time given as O(n log n). A proof for feasibility of the algorithm is presented.