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 <i>m</i> machines and serviced by <i>n</i> operators. In a job shop, different machines are 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 gien time. We have formulated several algorithms based on the knapsack and leader election problems to realize our goal each with O(m2) run-time complexity, where m is the number of machines. But we limit our discussion here to the np-hard knapsack problem.
