Minimizing the Number of Tardy Jobs in Flow Shop Sequence Dependent Setup Times Scheduling Problem

Mohsen Varmazyar; Nasser Salmasi

doi:10.4028/www.scientific.net/AMM.110-116.4063

Paper Titles

Overall Maintenance Time Reduction by Optimizing the Distance of Service Center in Manufacturing Unit through Single Facility Location Planning
p.4036

Hybrid System Model Simulation Framework for Cyber-Physical Systems
p.4043

An Investigation of Lean Implementation Status in Thai Manufacturing
p.4050

The Application Effect Analysis of Lean Production in China
p.4057

Minimizing the Number of Tardy Jobs in Flow Shop Sequence Dependent Setup Times Scheduling Problem
p.4063

Towards Lean Factory-Combining Lean Thinking with Promising Manufacturing Method - A Case of Finnish Boating Industry
p.4070

Research on Intelligent Variable Frequency of Air-Conditioner Control System Based on Fuzzy Control
p.4076

A New Fuzzy Approach for Minimizing Conveyer Stoppages in Mixed-Model Assembly Lines
p.4085

Metal Parts Visual Inspection Based on Production Rules
p.4091

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 110-116Minimizing the Number of Tardy Jobs in Flow Shop...

Minimizing the Number of Tardy Jobs in Flow Shop Sequence Dependent Setup Times Scheduling Problem

Abstract:

This paper investigates permutation flow shop scheduling problems with sequence-dependent setup times with minimizing the number of tardy jobs as criterion (F_m|prmu, S_ijk|∑U_j). Since the proposed research problem has been proven to be NP-hard, three different meta heuristic algorithms based on tabu search (TS) has been proposed to solve the problem. These three algorithms are different based on their tabu list characteristics. In order to evaluate the performance of the proposed TS algorithms, test problems in different ranges are generated to find the best algorithm. The comparison shows that the TS algorithm which its tabu list keeps track of the slots that the jobs are assigned has a better performance than the other algorithms

You might also be interested in these eBooks

Mechanical and Aerospace Engineering, ICMAE2011

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 110-116)

Pages:

4063-4069

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.110-116.4063

Citation:

Cite this paper

Online since:

October 2011

Authors:

Mohsen Varmazyar, Nasser Salmasi

Keywords:

Flow Shop Scheduling, Minimizing the Number of Tardy Jobs, Sequence-Dependent Setup Time, Tabu Search

Export:

RIS, BibTeX

Price:

Permissions:

Request Permissions

References

[1] S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, vol. 1, no. 1, p.61–68, March (1954).

DOI: 10.1002/nav.3800010110

Google Scholar

[2] Allahverdi and H.M. Soroush, The significance of reducing setup times/setup costs, European Journal of Operational Research, vol. 187, p.978–984, (2008).

DOI: 10.1016/j.ejor.2006.09.010

Google Scholar

[3] J.M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late, Management Science, vol. 15, p.102–109, (1968).

DOI: 10.1287/mnsc.15.1.102

Google Scholar

[4] A.M.A. Hariri and C.N. Potts, A branch and bound algorithm to minimize the number of late jobs in a permutation flow shop, European Journal of Operational Research, vol. 38, no. 228–37, (1989).

DOI: 10.1016/0377-2217(89)90108-2

Google Scholar

[5] J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker, Complexity of machine scheduling, Annals of Discrete Mathematics, vol. 1, p.343–62, (1977).

DOI: 10.1016/s0167-5060(08)70743-x

Google Scholar

[6] F. Della Croce, J.N.D. Gupta, and R. Tadei, Minimizing tardy jobs in a flowshop with common due date, European Journal of Operational Research, vol. 120, p.375–81, (2000).

DOI: 10.1016/s0377-2217(99)00164-2

Google Scholar

[7] C.S. Sung and Y.H. Kim, Minimizing due date related performance measures on two batch processing machines, European Journal of Operational Research, vol. 147, p.644–56, (2003).

DOI: 10.1016/s0377-2217(02)00352-1

Google Scholar

[8] R.L. Bulfin and R. M'Hallah, Minimizing the weighted number of tardy jobs on a two-machine flow shop, Computers & Operations Research, vol. 30, p.1887–900, (2003).

DOI: 10.1016/s0305-0548(02)00114-4

Google Scholar

[9] A.J. Ruiz-Torresa, J.H. Ablanedo-Rosasb, and C. Ho. Johnny, Minimizing the number of tardy jobs in the flow shop problem with operation and resource flexibility, , Computers & Operations Research, vol. 37, pp.282-291, (2010).

DOI: 10.1016/j.cor.2009.04.018

Google Scholar

[10] M.L. Pinedo, Scheduling, Theory, Algorithms, and Systems,: Prentice Hall, (2008).

Google Scholar

[11] F. Glover, Tabu search—Part I, ORSA Journal on Computing 1 (3) (1989), p.190–206.

DOI: 10.1287/ijoc.1.3.190

Google Scholar

[12] N. Salmasi, R. Logendran, and M.R. Skandari, Total flow time minimization in a flow shop sequence-dependent group scheduling problem, Computers & Operations Research, vol. 37, pp.199-212, (2010).

DOI: 10.1016/j.cor.2009.04.013

Google Scholar

[13] H.G. Campbell, R.A. Dudek, and M.L. Smith, A Heuristic Algorithm for the n-Job and m-Machine Sequencing Problem, Management Science, no. 16, pp.630-637, 1970. Figure 1. Feasible Solution.

DOI: 10.1287/mnsc.16.10.b630

Google Scholar