DEVELOPMENT OF HEURISTICS FOR SINGLE PROCESSOR SCHEDULING PROBLEMS WITH TARDINESS - RELATED PERFORMANCE MEASURES

Abstract

Scheduling problems involve the processing of jobs on processor(s) subject to constraints to optimise performance measures. Determining schedules that minimise tardiness-related performance measures for single processor scheduling problems is complex. Optimal-solutions require prohibitive-time, therefore heuristics are explored in real-life but effectiveness of existing heuristics is inadequate. The objective of this study was to develop effective heuristics for minimizing tardiness-related performance measures for single processor scheduling problems.

Six heuristics were developed and compared to the existing heuristics for minimizing the Total-Tardiness of jobs with Release-Dates (2TRD), Total-Tardiness and Total-Flowtime of jobs with Zero-Release-Dates (3TFZRD) and Total-Tardiness and Total-Flowtime of jobs with Release-Dates (3TFRD). HeuristicI (HeuI) and HeuristicII (HeuII) developed for 2TRD problem were compared to Dynamic Modified Due Date (DMDD). For 3TFZRD problem, heuristicIII (HeuIII) and heuristicIV (HeuIV) developed were compared to heuristicA (HeuA). Generalised Algorithm (GAlg) was compared to heuristicV (HeuV) and heuristicVI (HeuVI) developed for 3TFRD. HeuI and HeuII schedule jobs to reduce lateness. HeuIII and HeuIV reduce waiting-time. HeuV and HeuIV reduce idle-time and waiting-time. Fifty instances each, for problem-sizes (n) from small-sized (5≤n≤10), medium-sized (10<n<30), and large-sized (30≤n≤1000) randomly generated and industry-based problems involving 5, 10 and 15 jobs were solved in editor module in MATLAB environment. The Branch and Bound (BB) optimal method was used to solve small-and medium-sized problems. For 3TFZRD and 3TFRD problems, a composite-function was formulated and normalised. The Approximation Ratio (AR) test evaluated the heuristics’ effectiveness, significant differences were analysed using t-test at α_0.05.

The small-sized problems objective-function were: BB (9.26±9.12), HeuI (16.32±17.38), HeuII (12.03±10.02), DMDD (20.02±15.21) for 2TRD; BB (0.3059±0.0190), HeuIII (0.3059±0.0190), HeuIV (0.3192±0.0010), HeuA (0.3191±0.0200) for 3TFZRD; BB (0.1664±0.0043), HeuV (0.2350±0.0090), HeuVI (0.2096±0.0094), GAlg (0.3875±0.0380) for 3TFRD. HeuII, HeuIII and HeuVI yielded the AR of 1.85±1.22, 1.00±0.00 and 1.26±0.09 compared to DMDD (4.42±4.33), HeuA (1.05±0.013) and GAlg (2.33±0.176), respectively. The medium-sized problems objective-function were: BB (287.11±138.54), HeuI (442.15±197.36), HeuII (432.48±137.86), DMDD (449.03±135.54) for 2TRD; BB (0.3397±0.0047), HeuIII (0.3398±0.0201), HeuIV (0.3403±0.0204), HeuA (0.3629±0.0239) for 3TFZRD; BB (0.2410±0.0550), HeuV (0.3395±0.0520), HeuVI (0.3275±0.0530), GAlg (0.6191±0.0440) for 3TFRD. Considering the small-and-medium-sized problems, HeuII and HeuIII were not significantly different from the optimal. The large-sized problems objective-function were: HeuI (254,046±8215), HeuII (311,184±11,643), DMDD (303,044±8642) for 2TRD; HeuIII (0.3492±0.0024), HeuIV (0.3493±0.0024), HeuA (0.3736 ±0.0029) for 3TFZRD; HeuV (0.5511±0.0670), HeuVI (0.5473±0.0690), GAlg (0.7589±0.0960) for 3TFRD. Therefore, regarding 2TRD problem, HeuII was recommended when solving small-and-medium-sized problems and HeuI for large-sized. Considering 3TFZRD and 3TFRD problems, HeuIII and HeuVI were respectively recommended for all the problem sizes. With respect to the industry-based problems, HeuII, HeuIII and HeuVI were (44.3±36.9%), (182.7±113.8%) and (39.0±25.4%), respectively better than firm policies; First-Come-First-Served for 2TRD and 3TFZRD, Shortest-Processing-Time for 3TFRD.

The developed heuristics minimised tardiness-related performance measures for single processor scheduling problems and were more effective compared to the existing ones.

Keywords: Single Processor Scheduling, Heuristic, Effectiveness, Total-Tardiness, Total-Flowtime