One of the most popular heuristics used to solve the permutation flowshop scheduling problem (PFSP) is the NEH algorithm. The reasons for the NEH popularity are its simplicity, short calculation time, and good-quality approximations of the optimal solution for a wide range of PFSP instances. Since its development, many works have been published analysing various aspects of its performance and proposing its improvements. The NEH algorithm includes, however, one unspecified and unexamined feature that is related to the order of jobs with equal values of total processing time in an initial sequence. We examined this NEH aspect using all instances from Taillard’s and VRF benchmark sets. As presented in this paper, the sorting operation has a significant impact on the results obtained by the NEH algorithm. The reason for this is primarily the input sequence of jobs, but also the sorting algorithm itself. Following this observation, we have proposed two modifications of the original NEH algorithm dealing with sequencing of jobs with equal total processing time. Unfortunately, the simple procedures used did not always give better results than the classical NEH algorithm, which means that the problem of sequencing jobs with equal total processing time needs a smart approach and this is one of the promising directions for further research.

The aim of the work was to develop a prioritizing and scheduling method to be followed in small and medium-sized companies operating under conditions of non-rhythmic and nonrepeatable production. A system in which make to stock, make to order and engineer to order (MTS, MTO and ETO) tasks are carried out concurrently, referred to as a non-homogenous system, has been considered. Particular types of tasks have different priority indicators. Processes involved in the implementation of these tasks are dependent processes, which compete for access to resources. The work is based on the assumption that the developed procedure should be a universal tool that can be easily used by planners. It should also eliminate the intuitive manner of prioritizing tasks while providing a fast and easy to calculate way of obtaining an answer, i.e. a ready plan or schedule. As orders enter the system on an ongoing basis, the created plan and schedule should enable fast analysis of the result and make it possible to implement subsequent orders appearing in the system. The investigations were based on data from the non-homogenous production system functioning at the Experimental Plant of the Łukasiewicz Research Network – Institute of Ceramics and Building Materials, Refractory Materials Division – ICIMB. The developed procedure includes the following steps: 1 – Initial estimation of resource availability, 2 – MTS tasks planning, 3 – Production system capacity analysis, 4 – ETO tasks planning, 5 – MTO orders planning, 6 – Evaluation of the obtained schedule. The scheduling procedure is supported by KbRS (Knowledge-based Rescheduling System), which has been modified in functional terms for the needs of this work assumption.