================================================================================= (1) the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result, Towards Improved Dispatching Rules for Complex Shop Floor Scenarios - a Genetic Programming Approach ================================================================================= (2) author information Torsten Hildebrandt, hil@biba.uni-bremen.de, (+49) 421 / 218-5645 Jens Heger, heg@biba.uni-bremen.de, (+49) 421 / 218-9788 Bernd Scholz-Reiter, bsr@biba.uni-bremen.de, (+49) 421 / 218-5576 Bremen Institute of Production and Logistics – BIBA at the University of Bremen Hochschulring 20 28359 Bremen, Germany ================================================================================= (3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition), Torsten Hildebrandt ================================================================================= (4) the abstract of the paper(s), Developing dispatching rules for manufacturing systems is a tedious process, which is time- and cost-consuming. Since there is no good general rule for different scenarios and objectives automatic rule search mechanisms are investigated. In this paper an approach using Genetic Programming (GP) is presented. The priority rules generated by GP are evaluated on dynamic job shop scenarios from literature and compared with manually developed rules yielding very promising results also interesting for Simulation Optimization in general. ================================================================================= (5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies, (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. (G) The result solves a problem of indisputable difficulty in its field. ================================================================================= (6) a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission), (G): The problem tackled in our paper is that of dynamic job shop scheduling, which is well known to be np-complete (see, e.g., reference [24] in the paper). Due to the high importance of scheduling in industrial practice, developing heuristics for such problems is the subject of several decades of research. (B), (E), (F): To develop dispatching rules (as a special class of efficient, reactive/ online scheduling heuristics) has a long research tradition of its own. Over the years many researchers developed and published dispatching rules or investigated the advantages of different rules under various conditions. For our research we chose the well-researched dynamic job shop scenarios of Rajendran and Holthaus (reference [23] in our paper). In their paper Rajendran and Holthaus investigate the performance of various standard rules and also present manually developed, improved rules for their scenarios. In particular they present the PT+WINQ (Processing Time plus Work in Next Queue)-rule as the best rule to minimize the mean flow time of jobs. In a follow-up paper (reference [17]) Holthaus and Rajendran present the 2*PT+WINQ+NPT-rule (two times the Processing Time plus Work in Next Queue plus Next Processing Time) further improving upon their results. Their best rule is able to improve mean flow time over the standard SPT-Rule (Shortest Processing Time first; this rule is usually considered a good choice to minimize the flow time of jobs) by 6.3%. Using GP we were able to find rules improving their best result by another 8.5%, or compared to SPT by 14.3%. Furthermore GP-evolved rules turned out to remain considerably better than standard and benchmark rules even if they are applied to scenarios using a different number of machines and/or distributions of processing times and interarrival times. ================================================================================= (7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable); Torsten Hildebrandt, Jens Heger und Bernd Scholz-Reiter. Towards improved dispatching rules for complex shop floor scenarios-a genetic programming approach. In: Proceedings of the 2010 Genetic and Evolutionary Computation Conference (GECCO), Portland, USA, 2010. (accepted paper, to appear). ================================================================================= (8) a statement either that “any prize money, if any, is to be divided equally among the co-authors” OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors any prize money, if any, is to be paid to the corresponding author, Torsten Hildebrandt. ================================================================================= (9) a statement stating why the judges should consider the entry as “best” in comparison to other entries that may also be “human-competitive.” As we could show in our paper and further investigate in our current work, GP can help to capture the true potential of dispatching rule-based scheduling and offers a way to routinely create not just human-comparable but even better-than-human machine solutions for problems of high practical importance. As stated above using GP we were able to find considerably better rules than those developed manually for dynamic job shop scheduling. Industrial scheduling is a problem of high practical relevance and to solve it using dispatching-rule-based scheduling is very common, both in practice and academia. Many companies, especially in very capital- intensive industries like semi-conductor manufacturing, spend considerable time and money to select the best rule for their specific environments or spend even more effort to manually develop good rules. Especially the latter is a highly complex and time-consuming task. As our work could demonstrate GP can be used to largely automate this process and evolve rules performing even better than rules created manually. GP's results can very easily be added to the scheduling modules of current manufacturing control and manufacturing simulation software along existing rules. We apply GP coupled with a stochastic shop floor simulation of a complex shop floor scenario for fitness evaluation. This realistic and complex setting raises the issue of computationally very expensive fitness evaluations, because not only did we simulate our shop floor scenarios for a long time, usually many independent replications have to be carried out to obtain reliable estimates of rule performance. We therefore used a two step procedure to first use "lightweight" (but rather imprecise) evaluations of just a single replication during the GP run. In a second stage we identify the "truly" best rule later on using many independent replications to precisely assess the performance of the best rule of each generation. Best rules found by GP are better but usually also considerably larger than any manually developed rules found in the literature. Humans might be very good to identify relevant information for scheduling. How to properly integrate various pieces of information in a dispatching rule (also capturing the interdependence between decisions on many machines) however seems to be a task too complex for most humans. In our opinion to develop good dispatching rules for complex shop floor scenarios is therefore better left to an automated method such as GP. =================================================================================