A scheduling heuristic for simultaneous minimization of makespan and total weighted tardiness in the open shop setup

• Main Author: Siy, Eric A.
• Format: text
• Language: English
• Published: Animo Repository 1999
• Subjects: Scheduling (Management); Heauristic programming; Queuing theory; Industrial Engineering
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/2048
• Institution: De La Salle University

The Open Shop Scheduling problem is a decision on how to schedule n independent jobs on m independent machines (n greater than or equal to m) when deterministic processing times are given and there exists no predefined sequence of machines operations for each job. The specific criteria for good scheduling in this study is to simultaneously minimize makespan and total weighted tardiness. Earlier studies on the Open shop have focused on only one criterion--either makespan alone or total weighted tardiness alone. In these studies, makespan is minimized for the case of multiple machine setup, or else total weighted tardiness is minimized on one machine alone. The method of solution of earlier studies have usually been heuristic scheduling techniques or else branch-and-bound. The Open shop scheduling problem with more than two machines has been considered NP-Complete by many authors (Rinooy Kan, 1974 Garey and Johnson, 1976 Pinedo, 1995), which makes it practically impossible to use complete enumerative techniques to find an optimal solution. An approximation solution procedure or a heuristic was therefore needed. The study develops a heuristic procedure called Siy Open Shop Heuristic (SOSH) that simultaneously minimizes makespan and total weighed tardiness for the open shop. This study assumes that machine processing times, tardiness weights and due dates of all jobs are known. Furthermore, all jobs are assumed to be ready for scheduling at time=0. The heuristic begins by prescribing the sequence on the machine with the highest total processing time (H.T.P.T.) or simply hotpoint. This sequence is based on the highest weighted duespan of each job's due date. Duespan was defined in this study as the difference between the total processing times on the machine with the highest total processing time (i.e. minimum makespan) and the respective due dates of each job. After the sequence on the hotpoint machine has been prescribed, the sequences on the other machines are created following Latin square sequences. This results in a initial schedule. This schedule is then subjected to a weigh-and-improve process that checks for makespan and weighted tardiness of each job, and then identifying sequence changes that can lower makespan or total weighted tardiness. This sequence changes causes schedule improvements by inspecting how to insert tardy jobs earlier and/or delaying lighter weighted jobs. SOSH was compared against the minimizing total weighted tardiness heuristic (MTWT-OP) presented by Sule (1997) and was found to be more efficient due to having less computational operations and deriving superior schedules according to the dominance concept of Hammond, Keeney and Raiffa (1998). Equivalent if not superior schedules were found with SOSH on specific machines and job configurations. For small n x m cases, the recommended schedule may not be optimal, but could approximate the optimal one. It is even believed that for higher job-and-machines configurations, SOSH is able to find the optimal schedules. This was verified through complete enumeration of feasible schedules for each of the n x m cases.