Advanced Sequencing & Scheduling

This course is offered for graduate students at Master and Doctor of Enginnering program in Industrial Engineering at Morgan State University in Baltimore, Maryland. The Fall 2016 class consists of 5 MENG graduate students. It meets on Wednesdays from 5:30pm to 8:15pm in Schaeffer Engineering Building, Room 202.

This course covers job shop and flow shop scheduling problem for single and multiple machines. A major emphasis of the course is the S3 algorithm and its variations for n/3/F/Cmax problems. A research based approach will be implemented to encourage the students to learn how an algorithms is developed. Discussions on complexity of algorithms to enhance student understanding of the nature of combinatorial problems and why they are so difficult to solve in polynomial time will also be presented.

Additionally, a great emphasis is placed on implementing APA Styles in work submission by the students and encouraging students to submit abstracts to conferences.

Abstract Submitted to Conference

Improving Total and Maximum Tardiness in n/3/F/Cmax Problems

Minimizing completion time in a three machine flow-shop problem has been an interesting case among the combinatorial problems. Due its proven complexity, it has been classified as NP-hard problems. Yet, it has many features that one can take advantage of in finding a solution. Two of these characteristics are the symmetry of the problem and the fact that there are sequencing schedules that lead to optimal solution. Over the years, heuristic procedures are used to find good schedules. In 1988, a novel solution approach was introduced by Masud Salimian as part of a doctoral dissertation. The approach, Salimian’s Save and Spend (S3) algorithm builds the solution by identifying a job as the First Job, and adds jobs one at a time through special procedure to arrive at the final solution. On normal problems it always finds optimal solutions in an efficient manner. On extreme case problems, while it still finds the optimal solution, yet it becomes significantly in-efficient.

Due to structure of the algorithm, not only the solution for n/3/F/Cmax problem is arrived but it also provides an interesting option to deal with the job due dates by tweaking the final solution to improve total and maximum tardiness of the schedule. It uses the concepts of earliest due dates scheduling (EDD) and by exchanging jobs in the optimal schedule within the limits identified by S3 algorithm achieves its goal.

This paper explains the general S3 algorithm, introduces special set of metrics that can be used to identify whether a tardi job can be processed earlier in order to reduce total or maximum tardiness of the schedule. Examples demonstrating the procedure are also included.