Description

Progress Journal

Week 1 (May 25th)

Reading
- Artificial Intelligence: A Modern Approach (Second Edition) Chapter 4, Russell and Norvig 2003
- The Job-Shop Scheduling Problem Chapter 2, Dissertation by Jean-Paul Watson, Fall 2003
- Scheduling: Theory, Algorithms, and Systems (Second Edition) Chapter 7, Pinedo 2002
- Scheduling, Notes by Professor Adel Howe, Spring 2004

Professor Howe gave me an assignment from her graduate level course, where I was implementing a local search rather than the search from the original assignment. Since I was still trying to understand the problem and search algorithm I started out by listing the classes I thought I would need. I originally thought I had to use C++, so I began writting some of the simply code at the end of the week.

Week 2 (June 1)

Reading
- I re-read Chapter 2 of Jean-Paul Watson's dissertation since I found it very helpful
- I was also given code for the completed assignment from a graduate student. It took a while to read through this and understand what it does. This code was very helpful in learning about the Jop-Shop Problem and how to break it down. However this code implements a Tabu Search and my code will implement a local search.

This week I learned I was allowed to write the program in Java, which is a language I have much more experience with. Since I had not written much code, and I felt more comfortable using Java I switched over to that langauge. Making this switch might have delayed my completing the assignment slightly; however, I re-wrote the code mainly on my time back in the dorm.

Week 3 (June 7)

This week I finished writting the implementation of the local search algorithm for the Job-Shop Problem. I found on smaller problems the algorithm usually finds the optimal makespan. I used the example problem from Jean-Paul Watson dissertation which runs four jobs on three machines. A more well known problem is the Fisher and Thompson 10x10 instance. On this much larger example the algorithm does not seems to find the optimal makespan of 930, but rather numbers ranging from 1,200 to 1,400.

Week 4 (June 14)

Reading
- A Tutorial on Tabu Search, Herzt, Taillard and de Werra
- Scheduling: Theory, Algorithms, and Systems (Second Edition) Chapter 14.4, Pinedo 2002

After reading about the new algorithm I started to write the implementation. The Tabu Search is very similiar to the Local Search. The result should be closer to the optimal solution however because the Tabu Search is more complex. It keeps track of its previous moves so that it will not fall back into a local minimum.

Week 5 (June 21)

This was a busy week. I came in Saturday in an attempt to finish the Tabu Search Algorithm. I had a lot of difficulties with the timing of the operations. Once those were finally taken care of I noticed that the algorithm was swapping operations that were no longer on a critcial block. I fixed this by updating the moves list after each successful move.

Also this week Elaine Regelson, an instructor for the CS department, ran a seminar for high school women in an attempt to interest more women in the field and allow them to learn more about what makes computers interesting to women. The seminars included lectures then a snack break and lab time. It was assumed that none of the women had any programming experience. They started by making their own webpages with HTML. A few girls worked on that all week, but most of them wanted to move on to more advance things. By the end of the week many of the students had written more than one program in Java or C++ (some girls even used both.) People that stuck with just the one language try to move past programming "Hello World" and made calculators, madlibs, and even black jack. The sessions went so well Dr. Regelson is hoping to run a second session in July.

I also submitted my progress report for the DMP.

Week 6 (June 28)

Problem	Best Known	Tabu Search	Differ- ence
abz05	1,234	1,281	47
abz06	943	1,015	72
ft06	55	55	0
ft10	930	1,105	175
jpw43	32	32	0
la01	666	682	16
la02	655	698	43
la06	926	926	0
orb08	899	1,164	256
orb09	934	1,045	111

Reading
- A GRASP for Job Shop Scheduling, Binato, Hery, Loewenstern, and Resende
- Greedy Randomized Adaptive Search Procedures, Resende and Ribeiro

This week I finially worked out all the bugs in the Tabu Search. It did not actually start performing significantly better until I increased the number of random restarts to every 20 iterations. Some of the results can be seen in tha table to the right.

The problems where my implementation of the tabu search found the optimum are higlighted in white. It will always find the optimum for jpw43 and la06. Even though the Tabu Search only for the optium for 3 problems it performed much better than the local search. The solutions are much closer to the best known optimums and span a much smaller set of numbers. After completing this I moved on to GRASP algorithm.

Week 7 (July 5)

I wrote my implementation for the GRASP algorithm. This algorithm constructs a solution by inserting operations that will increase the makespan the least. It is clear this will rarely produce the optimal solution especially as the problem size increases. In order to find the optimal a local search is run on the completed solution.

In order to make the local search perform better I adjusted it to work with the N5 implementation. This allows the search to make less moves on the critical blocks. However when testing the adjusted local search the result were not much better than the N1 operator.

Week 8 (July 12)

When running the GRASP algorithm I found that on the larger problems it would take a great deal of time just to build the initial solution. So mush so that some problems took hours to run. In order to better the algorithm I added a timer and limited the time it could run. The program now allows the entire program 30 minutes to run and limits each run of the local search to 10 minutes. The results of this algorithm were close to the Tabu Search, but not as close to the optimal in most cases. Looking back over the different ways of improving GRASP, Professor Howe and I decided I should implement the Reactive GRASP algorithm.

Week 9 (July 19)

Problem	Best Known	Reactive GRASP	Percentage
abz05	1,234	1,287	4
abz06	943	1,026	9
ft06	55	56	2
ft10	930	1,171	26
jpw43	32	32	0
la01	666	681	2
la02	655	709	8
la06	926	926	0
orb08	899	1,214	35
orb09	934	1,112	19


Readings
- Re-read Greedy Randomized Adaptive Search Procedures, Resende and Ribeiro
- Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problem, Shaw

I completed the implementation of the Reactive GRASP. It performed almost as well as the Tabu Search. I had difficulty understanding the alpha parameter at first, but once I figured out how it effected the greediness of the search it was not hard to change the make GRASP reactive. Here are some of the results.

Week 10 (July 26)

Readings
- A Computational Study of the Job-Shop Scheduling Problem, Applegate and Cook

This week I read more about the Large Neighborhood Search even though I knew I would not have time to implement it. I wrote my final paper and worked on poster for Grace Hopper Reunion.

Final Report