Job shop operator scheduling software with change-over times Holden Milne & Dr. Opeyemi Adesina (Supervisor) Computer Information Systems - University of the Fraser Valley Abstract We present a solution to a variation of the Job Shop scheduling problem in which jobs (with each job having assigned priorities) are to be run by π‘š machines and serviced by 𝑛 operators. In a job shop, different machines run concurrently, which may result in multiple jobs being completed at the same time. It becomes a concern whenever jobs with lower priorities are serviced over jobs with higher priorities. Our goal is to develop a software to guide operators on jobs to be serviced at any given time. We have formulated several algorithms based on the knapsack and leader election problems to realize our goal each with O(π‘š2 ) runtime complexity, where π‘š is the number of machines. But we limit our discussion here to the np-hard knapsack problem. Background The issue we address considers a situation where at least two machines complete their cycles at almost the same time. An operator may spend time changing over a machine with lower priority while a machine with greater priority is left idle. In a job shop, time is money, therefore minimizing the service down time for high priority jobs becomes critical. This problem is similar to a well studied problem known as the Job Shop Problem. However, in this variant we are scheduling when the machines will be changed over by an operator. A key difference is that we have to account for the machines changeover time based on some user-defined priorities. Here we will discuss a solution formed around the Knapsack problem. The Knapsack Problem is where given a knapsack with capacity 𝐢 and a list of objects with known weights and values we want to find the optimal total value in the knapsack while keeping the total weight less than 𝐢. If the list of objects is infinite, the Knapsack Problem is unsolvable in a reasonable amount of time. If it is finite, however, it has many different solutions. Three important parameters about the machines we will be working with are. 1. Change-Over Time (𝐢𝑂𝑇) – The time it takes for an operator to make an idle machine runnable again. 2. Time to Completion (𝑇𝑇𝐢) – The time remaining for the machine to finish its run cycle. 3. Priority (𝑃) – The importance of the job the machine is currently executing. From these tests we can see that there is minimal loss to the makespan. This loss occurs as there may be some machines with lower 𝑃 and 𝑇𝑇𝐢 that get scheduled after another machine. From Figure 2, we can see this with how 𝑀1 has a 𝑇𝑇𝐢 + 𝐢𝑂𝑇 greater than the 𝑇𝑇𝐢 for 𝑀3. We do see a significant improvement on the idle time, which in our circumstance is more important than makespan. Lastly we also see a significant improvement in the weighted priority score, which is what we were looking to achieve. To achieve this we will define the following constraints. β€’ The schedule can be broken into smaller lists of ascending priority. Eg: (in Figure 2), 𝑀2 , 𝑀5 , 𝑀1 form one of these lists. β€’ For each machine 𝑀𝑖 and another machine π‘€π‘˜ in each smaller list, if π‘˜ < 𝑖 then πΆπ‘‚π‘‡π‘˜ + π‘‡π‘‡πΆπ‘˜ < 𝑇𝑇𝐢𝑖 . β€’ For each machine 𝑀𝑖 in each smaller list the sum of 𝐢𝑂𝑇 + 𝑇𝑇𝐢 of all machines scheduled before 𝑀𝑖 must be less than 𝑇𝑇𝐢𝑖 . In other words: π‘–βˆ’1 Figure 2: Example set of machines and the algorithm in process. Prior to any optimization, the time complexity of this algorithm runs at a worst case of 𝑂(π‘š2). Since the machine list will regularly need to be updated and requires sorting, our sorting becomes a lower bound of O(π‘š log π‘š) with the quicksort algorithm. Results Conclusions ෍(𝐢𝑂𝑇𝑗 +𝑇𝑇𝐢𝑗 ) < 𝑇𝑇𝐢𝑖 𝑗=1 These constraints will let us define our knapsack capacity and weights. This will be done dynamically by taking a specific machine’s 𝑇𝑇𝐢 as the capacity and the other machines 𝐢𝑂𝑇 + 𝑇𝑇𝐢 as the weights. We introduce a notation π‘₯. 𝑦 such that y is the attribute of object π‘₯ (e.g., 𝑀. 𝑇𝑇𝐢 implies the 𝑇𝑇𝐢 of machine 𝑀). Algorithm The algorithm works as follows: 1. Sort the list of machines by highest P, then by lowest 𝑇𝑇𝐢 then by lowest 𝐢𝑂𝑇. 2. Select pivot machine 𝑒 with the highest 𝑃 and the lowest 𝑇𝑇𝐢. Set 𝐢 to 𝑒. 𝑇𝑇𝐢. Initialize 𝐿 as an empty list. 3. For each machine 𝑣 with lower priority than 𝑒, in the same order as the input list: I. if 𝑣. 𝑇𝑇𝐢 + 𝑣. 𝐢𝑂𝑇 < 𝐢 then append 𝑣 to 𝐿, and subtract 𝑣. 𝑇𝑇𝐢 + 𝑣. 𝐢𝑂𝑇 from 𝐢. 4. Repeat from 2 on 𝐿 and also the elements not in 𝐿 separately until all machines have been scheduled, placing the elements in the first list before 𝑒 and the elements in the other list after 𝑒. This algorithm was tested in a Python3 Jupyter-Notebook environment on randomly generated sets of 40 machines. Machines were generated as 3-tuples – (𝐢𝑂𝑇, 𝑇𝑇𝐢, 𝑃) using random values. From the randomly generated list of machines we constructed a baseline schedule that sorted all machines by 𝑇𝑇𝐢. This gives us a good way to compare our algorithm to the first-come-first serve situation which is the basis for the problem. We ran 500 tests per metric and used a Ξ» = 0.9 for weighted priority. The worst-case time complexity for the algorithm of O(π‘š2) could cause problems. On one hand, in most circumstances, we will have relatively few machines. However, many of the applications of this algorithm are real-time and thus efficiency is important. Further analysis may allow us to bring this down by a constant factor, or possibly even to O(π‘š log π‘š) if possible. This algorithm will have applications in any situation where trying to optimize some parameters subject to time constraints with time delay. For example in a computer system where many programs a vying for a resource, like a finite number of data lines, and holding that resource for some amount of time, before processing the data independently. We could then use this algorithm to optimize the priority assigned to each program. The idea behind this algorithm is that by first selecting machines with the highest priority as our pivot machine, we can then place machines before this pivot so long as they will all complete before the pivot needs to be serviced. If they will not complete in time, they will be placed afterwards. This will ensure that by the time the high-priority pivot machine needs to be serviced, there will be an operator available. Figure 2 gives a case example showing the pivot machines and where the other machines in its list fall. Future Research Our goal will be to explore other optimization approaches such as Lagrange Multipliers, and the aforementioned Leader Election problem approach. Since the algorithm mentioned here is designed with only one operator and assumes that this will extend well to many operators, we may look at ways of improving this algorithm further if the number of operators is known. We will also look into ways of improving the time-complexity of this algorithm, and applying other knapsack problem solutions. Problem Formulation Our goal is to determine a change-over schedule where higher priority machines tend to be closer to the front of the schedule while ensuring that every machine will have a fair chance to get serviced. Thus we are trying to optimize priority subject to 𝑇𝑇𝐢 and 𝐢𝑂𝑇 constraints. To test this we will use a metric of weighted priority over the output list. This weights the priority of machines closer to the front of the list higher than those at the end. Acknowledgements Thank you to Dr. Adesina for the opportunity to work on this project, and the amazing advice and support he has given throughout. Thank you also to Harmonic Machine Inc. for giving us the opportunity to work on this problem and present results of this research. π‘š π‘Šπ‘’π‘–π‘”β„Žπ‘‘π‘’π‘‘π‘ƒπ‘Ÿπ‘–π‘œπ‘Ÿπ‘–π‘‘π‘¦ = ෍ 𝑃𝑖 βˆ™ λ𝑖 𝑖=1 Where 0 < Ξ» < 1 is the weighting parameter. It is important to ensure that our makespan and idle times are not severely harmed in the process. The makespan is the total time for all the machines to run and be serviced. The idle time is the time a completed machine must wait before being serviced. Our algorithm is tested against a first-come-first-serve baseline where machines are sorted by 𝑇𝑇𝐢. RESEARCH POSTER PRESENTATION DESIGN Β© 2019 www.PosterPresentations.com While there is an increase to makespan time, the large reduction in idle time and increase in weighted priority indicate a strong argument for the usage of this algorithm. One of the major draw backs of this approach is that machines with low priority and high change-over time may never be scheduled. For example if all machines have a max 𝑇𝑇𝐢 of 10 (the full cycle time of machines is no more than 10) and machine m has a 𝐢𝑂𝑇 of 11 machine m will always be scheduled last. However, we have already devised ways to handle these situations by allowing 𝑇𝑇𝐢 become negative if the machine sits idle, and using activation functions such as Rectified Linear Units to weight this negative descent. Figure 1: Partial psuedocode for main portion of the greedy-approach knapsack solution. An additional loop is required with this function. Figure 3: Baseline comparisons on 3 metrics.