Optimization of shop floor performance in job scheduling around a common due date

Abstract

Performance in job scheduling is an optimization problem in which ideal jobs are assigned to resources at particular times. A finite set of jobs is processed on a finite set of machines. Each job is characterized by a fixed processing time, each of which is to be processed on a multipurpose machine. The objective of this research is to improve shop floor performance through proper allocation of jobs in multi/single machines, taking due time into consideration, reduce the overall penalty and maximize the utilization time of the machine. Algorithms are developed for scheduling jobs in shop floor. In order to meet the required objectives, Deep Memory Greedy Search (DMGS) and Deep Memory with Particle Swarm Optimization (DMPSO) methods are proposed to solve the problem in multi machines. The obtained results are illustrated and the performance charts are plotted for visual analysis of the problem solving instances. The results demonstrate that the proposed algorithms on par with the benchmark results. Notably the time complexity of the DMGS algorithm is O(n log n). Even though the results of DMPSO are encouraging, the time complexity is not satisfactory. The Ratio Scheduling Algorithm (RSA), Robust Heuristic Algorithm (RHA) and Set-based PSO (SPSO) Algorithm are developed to allocate jobs on a single machine. The objective of the algorithms are to find an optimal schedule so as to minimize the earliness and tardiness penalties for a common due date d. The RHA algorithm will run in parallel, due to its divide and conquer nature. The RHA algorithm was applied to job size varying from 10 to 1000 and the results were compared with existing benchmark results. The RHA sorts the list in O(2log n) time. SPSO represents the problem by set-based representation scheme with the position and velocity of the particles defined by the related operators in discrete space. The result of SPSO is encouraging but it takes longer time to schedule the jobs. newline