The problem of scheduling in static flowshops is considered with the objective of minimizing mean or total tardiness of jobs. A heuristic algorithm based on the simulated annealing (SA) technique is developed. The salient features of the proposed SA algorithm are the development of two new perturbation schemes for use in the proposed SA algorithm and a new improvement scheme to improve the quality of the solutions. The proposed algorithm is evaluated by using the bench-mark problems available in the literature. The performance of the proposed SA algorithm is found to be very good, and the proposed heuristic performs better than the existing heuristics.

Chandrasekharan Rajendran

Department of Management Studies

Algorithms

Computational complexity

Heuristic methods

Job analysis

Perturbation techniques

Problem solving

scheduling

Simulated annealing

FLOWSHOPS

NEAR-OPTIMAL METHODS

TOTAL TARDINESS (TARD)

Computer aided manufacturing

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Scheduling in flowshops to minimize total tardiness of jobs

International Journal of Production Research

This paper addresses the problem of dispatching in flowshops with bottleneck machines. The presence of bottleneck machines results in the restricted throughput in flowshops. The objective is to develop dispatching rules for scheduling by taking into account the presence of bottleneck machines. The measures of performance are the minimization of total flowtime of jobs, the minimization of the sum of earliness and tardiness of jobs, and the minimization of total tardiness of jobs, considered separately. Many existing conventional dispatching rules and the proposed dispatching rules have been extensively investigated for their performance by generating a large number of problems of various sizes and bottleneck conditions. The results of the experimental investigation show that the proposed dispatching rules emerge to be superior to the conventional dispatching rules. © 2006 Elsevier Ltd. All rights reserved.

Computers and Industrial Engineering

Dispatching in flowshops with bottleneck machines

The Economic Lot Scheduling Problem (ELSP) on a single facility (or machine) with the time-varying lot-sizes approach and with sequence- independent/sequence-dependent setup times of parts or products is studied in this paper. The objective is to minimise the long-run average inventory carrying cost and setup costs of products. While the frequency of production of a product is determined from an existing heuristic, we allow for possible changes in the heuristically computed frequencies of parts (or products) and hence attempt to reduce the total cost per cycle during the metaheuristic search process. Three metaheuristics, namely, a Genetic Algorithm (GA), a Simulated-annealing Algorithm (SA) and an Ant-Colony Algorithm (ACA) are proposed. A new crossover operator is designed and incorporated in the proposed GA. New perturbation schemes are incorporated in the proposed SA. In the proposed ACA, the initialisation and updating of pheromone intensity (or trails) are done subject to certain conditions presented in this work. The best-performing existing heuristic algorithm and the proposed algorithms for ELSP with sequence-independent setup times of products are evaluated by considering a couple of benchmark problems and by generating many problems with different number of products and comparing the solutions. In addition, we consider the case of sequence-dependent setup times and the associated setup costs. The performances of the existing algorithm and the proposed algorithms are evaluated by considering a proposed (computationally simple) lower bound on total cost per cycle with the consideration of sequence-dependent setup times and the associated setup costs of products. The computational performance analyses reveal the effectiveness of the proposed metaheuristics. © 2007 Inderscience Enterprises Ltd.

European Journal of Industrial Engineering

Metaheuristics for solving economic lot scheduling problems (ELSP) using time-varying lot-sizes approach

The problem of scheduling in a flowshop, where setup, processing and removal times are separable, is considered with the objective of minimizing makespan. Heuristic algorithms are developed by the introduction of simplifying assumptions into the scheduling problem under study. An improvement method is incorporated in the heuristics to enhance the quality of their solutions. The proposed heuristics and an existing heuristic are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various values of parameters are presented. © 1997 Taylor & Francis Ltd.

Production Planning and Control

Heuristics for scheduling in a flowshop with setup, processing and removal times separated

Most of the heuristics for flowshop scheduling aim at minimizing makespan. However, scheduling with multiple objectives, such as that of minimizing makespan, total flowtime and machine idletime, is more effective in reducing the total scheduling cost. In this article, we first address the problem of scheduling to minimize makespan and total flowtime, and propose a new heuristic algorithm. A heuristic preference relation is developed as the basis for the heuristic so that only the potential job interchanges are checked for possible improvement with respect to these two objectives. The proposed as well as the existing heuristics are evaluated in a large number of randomly generated large-sized problems. The proposed heuristic algorithm is then extended to cover the problem of scheduling to minimize makespan, total flowtime and machine idletime. The results of the experimental investigation of the evaluation of this heuristic algorithm and the existing heuristic in meeting these objectives are also reported. It is found that both the proposed heuristics are more effective than the existing one for scheduling with multiple objectives. © 1995.

European Journal of Operational Research

Heuristics for scheduling in flowshop with multiple objectives

Constructive and composite heuristic solutions to the P//∑Ci scheduling problem

Sequencing CONWIP flow-shops: Analysis and heuristics

Computers & Operations Research

Tabu search for total tardiness minimization in flowshop scheduling problems

Journal	International Journal of Production Research
ISSN	00207543
Open Access	No