An Effective Heuristic to Reduce Total Flowtime for Randomly-Structured Flowshop Problems

We propose a heuristic to reduce total flowtime in a six-job, four-machine permutation flowshop scheduling problem.This work contributes to the prolific research efforts reported in the permutation flowshop scheduling problem (PFSP).The heuristic logic generally produced a good solution in each randomly structured flowshop, by following sequencing rules for scheduling a given job earlier or later in the sequence being constructed.Through this method we obtain a unique job schedule.We utilized Microsoft Excel to generate each six-job, four-machine randomly structured flowshop scheduling problem.The job completion time matrix was randomly structured; each completion time was modeled using an integer uniform distribution in the interval 1,100.A complete enumeration of 720 sequences was generated using Excel's Visual Basic application so that the resulting solutions could be compared to the optimal.With the goal of evaluating the performance measures produced by the heuristic, the minimum flowtime, mean flowtime, maximum flowtime, the standard deviation, the sequence generated by the heuristic, the ordinal rank of the resulting flowtime, and the percentile rank of the resulting flowtime were recorded for 102 flowshop problems.Since our objective was to reduce flowtime, a low percentile rank was considered desirable.When applying the heuristic, any ties in the decision rules were resolved lexicographically.The heuristic produced a flowtime F* ordinal rank in a single partial sequential logical process.The application of the heuristic systematically generated near-optimal, or optimal solutions: An analysis of the computational results indicates that 50 percent of F* ordinal ranks generated fell in