LIBRARIES Slack-based Lower Bound and Heuristic

This paper addresses optimal job sequencing decisions for various classes of permutation flowshops. We first describe a framework to classify flowshop scheduling problems based on the level of intermediate storage, job transfer mechanism, and objective function. We discuss the interrelationships between various flowshop models, develop a new slack-based lower bound for the total processing time of each machine, and describe an assignment-patching heuristic to generate effective job sequences. Our computational results show that, compared to previous approaches, the slack-based lower bound is effective when job processing times are random or have a trend, and the assignment-patching heuristic performs well for all models. By locally improving the heuristic solution using a two-exchange procedure, we are able to generate solutions that ai^e within 10 % from optimal for most scenarios