A flowshop is a manufacturing environment with unidirectional flow of jobs through the various machines that are arranged in the order of job processing. A flowline-based manufacturing system (FBMS) is characterized by the flowline-based layout of machines with the machines arranged in the order of processing of jobs, but with the possibility of some or all jobs having missing operations on some machines. The significance of non-permutation schedules (NPS) and their effect on improving the schedule performance measures, in the context of FBMS, is highlighted in this paper. A simple heuristic procedure to derive NPS from a given permutation schedule is proposed. Results of the extensive computational experimentation, with makespan as the primary criterion and total flowtime as the secondary criterion, are presented. The results show that the proposed heuristic procedure for generating non-permutation schedule set is effective and improves the schedule performance measures with minimal computational effort. © 2002 Elsevier Science Ltd. All rights reserved.