| Article ID: | iaor1992964 |
| Country: | United Kingdom |
| Volume: | 18 |
| Start Page Number: | 635 |
| End Page Number: | 643 |
| Publication Date: | Dec 1991 |
| Journal: | Computers and Operations Research |
| Authors: | Bard Jonathan F., Feo Thomas A., Venkatraman Krishnamurthi |
| Keywords: | heuristics |
A greedy randomized adaptive search procedure (GRASP) is presented for an unusually difficult single machine scheduling problem with flow time and earliness penalities. Previous methods reported in the literature provide optimal solutions to problems with up to only 14 jobs. GRASP constructs an optimal solution typically within 10s of CPU time on a personal computer for 58 out of the 60 problems tested with 30 jobs. For the remaining instances, the method provides a solution extremely close to the optimal.