Search

This paper presents a heuristic algorithm to solve flow shop scheduling problems (FSSP) with the criterion to minimise the system utilisation time with minimum of maximum completion time (makespan)...

Permutation flowshop scheduling problems (PFSSP) with an objective to minimise the total elapsed time (makespan), are typically NP-hard in nature. Many heuristics and metaheuristics have been designed and developed to optimise makespan in flowshop scheduling environment. Better quality of metaheuristic approach depends on solution obtained by heuristic. In this paper, a nature inspired heuristic based on the biological characteristics of desert sparrow is proposed to optimise makespan in flowshop environment. The cooperative task allocation nature of desert sparrow is the basis to find the best initial feasible solution. Computational analysis depicts that proposed heuristic gives significantly better results than referred heuristics for the considered problem.

This paper propounds the bi-criteria scheduling problem with identical parallel machines, volatile due dates and processing times. A robust and simple structured nature inspired approach has been applied for minimisation of maximum tardiness as the primary and the number of tardy jobs as the secondary criteria. The optimal values of both criteria are evaluated on the trot confined with a constraint that optimal value of secondary criteria does not infringe the primary criteria in the opposite sense of the requirement. To unfold such kind of NP hard optimisation problems, genetic algorithm (GA) has shown a great advantage in solving the combinatorial optimisation problems in view of its characteristic that has high efficiency and is the best fit for practical application. In this paper, a multi-step crossover fusion operator of genetic algorithms (MSXF) has been introduced and applied to a set of randomly generated problems of different sizes. The results obtained are correlated with the other crossover operators. Computational results show that MSXF operator outperforms all the most every time on randomly generated problems analogous to the parameter under consideration.

An improvement heuristic algorithm is proposed in this paper for solving flow shop scheduling problem (Fm / prmu / Cmax). To test its efficiency, firstly the performance of the proposed algorithm is done against the six heuristics existing in the literature including the best NEH heuristic on 120 Taillard benchmarks. Further, this set of 120 Taillard instances is increased to 266 benchmark problem instances which include Carlier's, some Reeves and some new hard VRF instances from Vallada et al. (2015). On these instances, the performance of the proposed algorithm is tested against the best NEH and the famous CDS heuristic with the best known upper bounds. Further, a brief analysis of the other heuristics and metaheuristics existing in literature is done on Taillard problem instances. The proposed heuristic outperforms all the heuristics reported in this paper.

The aim of this paper is to introduce the concept of arbitrary lags in n-jobs, m machines flowshop scheduling problem involving the processing times and transportation times of jobs. Start lag is the minimum time which must elapse between starting of job i on the first machine and starting of job i on the last machine. The stop lag for the job i is the minimum time which must elapse between completing job i on the first machine and completing it on the last machine. The concept of fuzzy processing time to represent the uncertainty, vagueness in processing of jobs is introduced. An algorithm to find the optimal sequence so as to minimise the total elapsed time subject to some specified lag time constraint is discussed. A numerical illustration is given to demonstrate the computational efficiency of proposed algorithm as a valuable analytical tool for the researchers.

Flow shop scheduling with sequence-dependent setup time is the most complicated case of scheduling of jobs. The operational cost of machines is related to the setup time required for processing of jobs on different machines. To express the randomness probabilities are associated with processing times of different attributes on given machines. The objective is to schedule n-jobs on m-machines to minimise operational cost of machines subject to minimum total elapsed time of jobs in a flow shop whenever the setup times on machines are sequence-dependent. As the problem is NP-hard, a heuristic algorithm is proposed to find the latest time so as to reduce operating time and hence the operational cost with minimum makespan. A numerical example is also given to substantiate the algorithm.

Parallel machine scheduling and its complex combinatorial optimisation problems are widely studied. A lot of research has been carried out in this area to determine how to effectively schedule parallel execution of different jobs to be carried out using different machines in order to achieve the optimisation criteria. In this paper, the formulations of multi-objective flower pollination algorithm obtained by the combination of weighted objectives or secondary storage for managing possible solutions along with their hybrids with genetic algorithm have been developed and applied to the problem of scheduling jobs on machines running in parallel in order to optimise bi-criteria, namely, maximum tardiness and weighted flow time. It has been empirically verified that multi-objective flower pollination algorithm using secondary storage and hybridised with genetic algorithm leads to better results as compared to the existing algorithms. The results obtained have been verified by numerical illustrations and statistical tests.

This paper is an attempt to study the steady state analysis of a complex network of queues in which a common server is linked in series with each of two parallel biserial servers. The arrival and service pattern follows Poisson law. The generating function technique, law of calculus and statistical tools have been used to find the various queue characteristics. The model finds its application in decision making, in process industry, in banking system, in communication networking, in supermarkets, in healthcare centre and in many administrative setups. An algorithm is proposed to find the mean queue length of customers/jobs, variance of queues and average waiting time of customers/jobs. The performance of algorithm is assessed by a numerical illustration.

In today’s information age society, where activities are highly interdependent and intertwined, sharing of resources and hence waiting in queues is a common phenomenon that occurs in every facet of our lives. Flowshop scheduling with an objective of minimising the makespan is also an important task in manufacturing system. The present paper is an attempt to establish a linkage network of queues consisting of a biserial server and two parallel servers linked to a common server in series with a multistage flow shop scheduling system. The arrival and service pattern follow Poisson law. The completion time of jobs/customers in queue network (phase I of the service) will be the setup time for first machine in flowshop system having ‘m’ machines in series (phase II of the service). A heuristic approach to find optimal or near optimal sequence of jobs processing minimising the total elapsed time with minimum waiting time has been discussed for the queuing-scheduling linkage model. The performance of the algorithm is evaluated by a numerical illustration.

This paper pertains to a bicriteria scheduling problem on parallel machines which minimises the weighted flowtime (WFT) with the condition that primary criteria of Tmax remains optimised. The processing times of jobs are in fuzzy environment and are represented by triangular fuzzy numbers. The membership function of fuzzy processing times denotes the grades of satisfaction with respect to completion times of jobs. The objective of this paper is to schedule jobs on parallel, identical machines so as to minimise the secondary criteria of WFT without violating the primary criteria of maximum tardiness (Tmax). Following the theoretical treatment, we provide numerical example(s) to demonstrate that the proposed algorithm has potential as a valuable analytical tool for researchers.

In recent years, urban air pollution has emerged as an acute problem because of its negative effect on health and living conditions. Regional air quality problems, in general, are linked to violations of specified air quality standards. The current study aims to find neural network based air quality predictors, which can work with a limited number of datasets and are robust enough to handle data with noise and errors. A number of available variations of neural network models, such as the Recurrent Network Model (RNM), the Change Point Detection Model with RNM (CPDM), the Sequential Network Construction Model (SNCM), the Self Organising Feature Model (SOFM), and the Moving Window Model (MWM), were implemented using MATLAB software for predicting air quality. Developed models were run to simulate and forecast based on the annual average data for 15 years from 1985 to 1999 for seven parameters, viz. VOC, NOx, CO, SO2, PM10, PM2.5 and NH3 for one county of California, USA. The models were fitted with first nine years of data to predict data for remaining six years. The models, in general, could predict air quality patterns with modest accuracy. However, the SOFM model performed extremely well in comparison with the other models for predicting long-term (annual) data.