|The Scheduling Problem|
In today's complex manufacturing setting, with multiple lines of products, each requiring many different steps and machines for completion, the decision maker for the manufacturing plant must find a way to successfully manage resources in order to produce products in the most efficient way possible. The decision maker needs to design a production schedule that promotes on-time delivery, and minimizes objectives such as the flow time of a product. Out of these concerns grew an area of studies known as the scheduling problems.
Scheduling problems involve solving for the optimal schedule under various objectives, different machine environments and characteristics of the jobs. Refer to the Definitions page for terminology. In this web site, we offer the user the chance to try different combinations of objectives, environments, and characteristics in creating his or her own scheduling problems and testing the performance of various algorithms in his or her cases. In some combinations, where optimal algorithms exist, our solver will return the "best" schedule to the user as long as he or she chooses the optimal algorithm for application. In other cases, where only a heuristic approach exists, our solver will return a "good" schedule to the user. In general, our solver allows the user to apply any algorithm to any objective, provided there are no conflicts between the inputs to the algorithm and the objective. The user can see for themselves the myriad of schedules that can result under different sets of rules.
Some of the objectives that the users can choose from include minimizing the makespan, or the last completion time of a job, minimizing the total completion time of all jobs, and minimizing the total "lateness" of jobs. A complete listing and detailed explanation of each objective can be found in the Objectives page. The user can select any number of jobs and any number of parallel machines. A complete description of machine environments can be found in the Environments page. Other parameters such as due dates, and weights of the job can also be specified. Different algorithms are also provided for users to choose from. Included in this site are a collection of list scheduling algorithms, including Shortest Processing Time and Longest Processing Time. Other classes of scheduling algorithms, such as Hodgson's Algorithm and Johnson's Algorithm, are also available. Refer to the Algorithms page for a comprehensive listing. Scheduling and sequencing jobs have a wide variety of applications, from designing the product flow and order in a manufacturing facility to modeling queues in service industries. It is indeed a useful subject that is still being actively researched. This project is created by , under the supervision of Professor Dorit S. Hochbaum . It is supported by the National Science Foundation through its award for undergraduate research (No. DMI-9713482). Questions or comments? Send mail to Professor Hochbaum. .