We focus on a problem maximizing the total weight of just-in-time jobs under multi-slot conditions. In just-in-time scheduling, each job has to be completed exactly on its due date. Since just-in-time scheduling has applications to both manufacturing and computer systems, a number of research papers on such scheduling problems exist. Under multi-slot conditions, each job has one due date per time slot and has to be completed just-in-time on one of its due dates. We assume that each job has a certain weight per time slot, and the weight is non-increasing with increasing completion time for each job. This problem maximizing the total weight of just-in-time jobs under multi-slot conditions was recently proven to be NP-hard. Our research presents two heuristics for this problem. The first is a simple greedy algorithm, in which each job is scheduled in the order of largest to smallest on weight for each time slot. The second applies a well-known algorithm for a weighted interval scheduling problem to this problem. We implement the two heuristics, and compare their performances from computational experimentation.
Track: Operations Research
Published in: 8th Annual International Conference on Industrial Engineering and Operations Management, Bandung, Indonesia
Publisher: IEOM Society International
Date of Conference: March 6
-8
, 2018
ISBN: 978-1-5323-5944-6
ISSN/E-ISSN: 2169-8767