Optimization of Job Shop Scheduling Problems in Cellular Manufacturing Systems

Download Full-Text PDF Cite this Publication

Text Only Version

Optimization of Job Shop Scheduling Problems in Cellular Manufacturing Systems

  1. Dhakshina Murthy 1*, S. Dhineshkumar2*,

    1. Arulselvan3*, P. Bharathi 4 *

      (1, 2, 3, 4)- UG Scholar, Department of Mechanical Engineering,

      Hindusthan Institute of Technology, Coimbatore-641032, Tamil Nadu, India.

      Abstract: Nowadays, there is a strong tendency towards the effectiveness of manufacturing system. Proper scheduling (determining the sequence in which operations are to be performed) of job is indispensable for the successful of operation of a shop. Group Technology (GT) has become an increasingly popular concept in manufacturing, which is designed to take advantage of mass production layout and techniques in smaller batch production system. Since the conven- tional scheduling methods need more computation time an attempt has been made to optimize the scheduling for Cellular Manufacturing System. In this different types of products in the job shop environment are identified and grouping of cells is performed using Rank Order Clustering (ROC) method. In the second part, optimization procedure has been developed for the scheduling problem for processing in the machine cells for exploring the optimum schedule by minimizing the total penalty cost due to the delay in meeting the due date.

      Keywords: Scheduling, Group Technology, Cellular Manufacturing, Rank Order Clustering

      1. INTRODUCTION

        Increased competition and fluctuating market demands have driven many manufacturing firms to consider novel approaches to improve productivity and eliminate waste. In the past two decades, manufacturing industries have undergone a revolution, widely consider as the third industrial revolution. Many innovative concepts have surfaced only few among them have been successful. The concept of Group Technology (GT) is the exploitation of the similarities among processes and component design in such way that it increases the utilization of resources, and eliminates/reduces non value added activities, i.e. material handling, scraps, downtime, etc. GT ex- ploits similarities in three different ways:

        1. by performing like activities together,

        2. by standardizing similar tasks and (iii) by efficiently storing and retrieving infor- mation about recurring problems. GT forms the basis of Cellular Manufacturing Systems (CMS).

        Cellular manufacturing is a prac- tice that involves grouping similar ma- chines into cells, simultaneously grouping similar components into groups. The CMS offer a great deal of benefits including re- duction in material handling times, setup times, lower work in progress and im- proved quality and less re-work, higher productivity,

        K. Kalidas 5*

        5- Associate Professor, Department of Mechanical Engineering,

        Hindusthan Institute of Technology, Coimbatore-641032, Tamil Nadu, India.

        increased job status visibility, improved job satisfaction for operators, centralization of responsibilities, simpli- fied planning and control procedure. Cell formation, cell layout and scheduling of jobs in a cell are three operating decisions that must be made when implementing a cellular manufacturing system (CMS). Cell formation and cell layout of design issues while job scheduling is the production planning and control issue. A cell can gen- erally be classified as a flow line type or a job shop type according to process similar- ities of parts in a cell.

        Flow line cells usually have more simplified product flows due to higher part similarity. The job shop cell is an alterna- tive for providing more flexibility. The fact that a job shop cell has more flex- ibility and can added to a more diverse range of part sub families accounts for its interest in the arena of the expanding product diversity. However, planning and controlling activities in a job shop cell are more difficult due to its higher operational complexity. As indicated in group schedul- ing procedures in exploit similar setups that exist among individual parts within a part family. Bottleneck management is quite effective in planning and scheduling the job shop with load imbalance. An im- properly scheduled and managed bottle- neck is likely to incur a significant loss on the shop floor. Several approaches to grouping machines part families have emerged.

        A comprehensive review and dis- cussion on different approaches in ma- chine part families formation in GT can be found in Offodile et al. In a typical CMS environment, however, there could be some exceptional parts, which need to visit machines in the other cells. This fact limits the applicability of group scheduling approaches. This paper addresses the scheduling manufacturing cells in which parts may need to visit different cells.

        One of the most important issues to attain benefits of CMS is effective im- plementation of its scheduling system. Nevertheless, this area not been widely attempted in literature as compared to the cell information problem. Due to the simi- larities in the design, shape, function, etc., parts in part family generally visit machine in same sequence with minor differences in setup requirements. Therefore a part family can be divided into several groups so that the each group needs similar setup requirements. In other words a group is a sub set of a part family and all parts in the same group needed similar setup requirements.

        This problem is addressed as job shop group scheduling or briefly group schedul- ing in the literature in group scheduling it is assumed that each part family can be processed in one cell by duplicating bot- tleneck machines or subcontracting excep- tional parts. However, subcontracting ex- ceptional parts may not be practical or du- plicating bottleneck machines may not be possible in every CMS environment due to production economic, budget and manu- facturing space limitation etc. Thus in a typical CMS environment, it is difficult to form independent manufacturing cells and mostly there are some exceptional parts that create inter-cellular moves. These constraints limit the applicability of group scheduling methods in real life. Examines three array- based clustering algorithms, namely rank order clustering (ROC), rank ordering clustering-2 (ROC-2) direct clus- tering analysis (DCA) for manufacturing cell formation, with a real life example 2 demonstrate the effectiveness of various structure in algorithm and present a simu- lated annealing (SA) based algorithm has been developed for scheduling of parts with in a cell for the objective of minimi- zation of weighted sum of makes span, flow time and ideal time.

        To our knowledge, no previous study span incorporated both cells infor- mation in the scheduling of jobs in job shop cells. The study proposes a two stage scheduling procedure in a job shop cell. This paper considers a scheduling problem in which intercellular moves are allowed and parts may visit machines in the other cells. This research proposes a meta- heuristic namely Scatter Search method to solve the problem. The literature shows Scatter Search method to perform better for scheduling problems. In the first part of this work different type of product in the job shop environment are identified and grouping of cells is performed using Rank Order Clustering method. In the second part optimization procedure has been de- veloped for the scheduling problem for processing in the machine cells. For keeping the machine sequence fixed as per the cell layout and change the job se- quence optimum penalty cost.

        This paper is organized as follows: In section 2, the scheduling problem is de- scribed and formulated. Section

        3 de- cribed the cell formation using Rank Or- der Clustering technique and penalty cost in this work. The computational results of proposed algorithms are reported in sec- tion 6. Section 7 contains conclusion.

        Batch manufacturing is estimated to be the most common form of production in the United States, constituting more than 50% of total manufacturing activity. There is a growing need to make hatch manufacturing more efficient and produc-

        tive. In addition, there is an increasing trend toward achieving a higher level of integration between the designs and manu- facturing functions in a firm.

      2. DATA REQUIREMENTS

        • n number of jobs.

        • m number of machines.

        • Process sequence- the order by which the processes are to be per- formed.

        • Processing time for all the products on each machine.

        • Batch quantity required for each job.

        • Target dates.

        • Penalty in Rupees per day per part.

      3. DATA COLLECTED Table 1 Time taken for machining the job

        Job Name

        Jobs No

        Shaper

        Lathe

        Milling

        Boring

        Welding

        Grinding

        Processing Time in Mins

        Nut

        1

        0

        17

        0

        0

        0

        0

        Bolt

        2

        0

        20

        0

        0

        0

        0

        Gear

        3

        60

        19

        30

        15

        0

        4

        Hexagonal Gear

        4

        65

        18

        45

        4

        0

        6

        Flange Pipe

        5

        0

        50

        35

        35

        27

        25

        Screw

        6

        62

        58

        15

        0

        0

        0

        Lead Screw

        7

        60

        35

        20

        0

        0

        0

        Universal Coupling

        8

        60

        18

        20

        10

        0

        6

        Lathe Centre

        9

        63

        30

        0

        0

        0

        5

        Piston Connecting Rod

        10

        0

        0

        17

        11

        0

        7

        Sprocket

        11

        0

        0

        15

        55

        0

        5

        Tie Rod End

        12

        0

        26

        28

        27

        0

        7

        Gear Pump Flange

        13

        0

        27

        15

        31

        17

        5

        Table 2 6 Machines and 13 Jobs Scheduling Problem

        Job

        Process Sequence (Machining time in min.)

        Due Date

        Batch Quantity

        Penalty

        / day/item (Rs.)

        1

        2(17)

        5

        200

        1

        2

        2(20)

        5

        200

        1

        3

        1(60)-2(19)-3(30)-4(15)-6(4)

        10

        100

        15

        4

        1(65)-2(18)-3(45)-4(4)-6(6)

        10

        100

        15

        5

        2(50)-3(35)-4(35)-5(27)-6(25)

        12

        100

        20

        6

        1(62)-2(58)-3(15)

        10

        100

        15

        7

        1(60)-2(35)-3(20)

        10

        100

        10

        8

        1(60)-2(18)-3(20)-4(10)-6(6)

        10

        100

        10

        9

        1(63)-2(30)-6(5)

        8

        100

        10

        10

        3(17)-4(11)-6(7)

        5

        100

        5

        11

        3(15)-4(55)-6(5)

        8

        100

        10

        12

        2(26)-3(28)-4(27)-6(7)

        8

        100

        10

        13

        2(27)-3(15)-4(31)-5(17)-6(5)

        8

        100

        10

      4. RANK ORDER CLUSTERING TECHNIQUE

It is specifically applicable in pro- duction flow analysis. It is an efficient and easy-to-use algorithm for grouping ma- chines into cells. In a starting part-machine incidence matrix that might be compiled to document the part in a machine shop (or other job shop), the occupied locations in the matrix are organized in a seemingly random fashion. Rank order clustering works by reducing the part-machine inci- dence matrix to a set of diagonal zed blocks that represent part families and as- sociated machine groups. Starting with an initial parts of machine incidence matrix. The algorithms consist of the following steps:

    1. STEPS

      1. Each row of the matrix. Read the series of ls and 0s from left to right as a binary number. Rank the rows in 0l if decreasing value. In case of a tie, rank the rows in the same order as they appear in the current matrix. Numbering from top to bottom,

        is the current order of rows the same as the rank order determined in the previous step? If yes, go to step 7, if no, go to the following step.

      2. Reorder the rows in the part- machine incidence matrix by listing them in decreasing rank order, starting from the top.

      3. Each column to be matrix. Read the series of 1's and 0's from top to bottom as a binary number. Rank the columns in order of decreasing value, in case of a tie. Rank the columns in the same order as they appear in the current matrix.

      4. Numbering from left to right, is the current order of columns the same as the rank order determined in the previous step? If yes go to step 7. If no go to the following step.

      5. Reorder the columns in the part- machine incidence matrix by lining them in decreasing rank order, starting with the left column. Go to step 1.

      6. Stop

    2. CELL FORMULATION

Step 1: For each row of machine part matrix, assign binary weight and cal- culate the decimal weight.

Step 2: Sort out the rows of the bina- ry matrix decreasing order of the cor- responding decimal weight.

Step 3: Repeat the preceding two steps for each column. Step 4: Repeat the steps so that the position of each element in each row and column does not change.

    1. RANK ORDER CLUSTERING STEP 1

      Job Machine

      Nut

      Bol t

      Gea r

      Hexagona l Gear

      Flange Pipe

      Scre w

      Lead Scre w

      Univers al Couplin g

      Lathe Centre

      Piston Connectin g Rod

      Sprocke t

      Tie Ro d En

      d

      Gear Pump Flange

      Decim al

      weight

      Rank

      Shaper

      0

      0

      1

      1

      0

      1

      1

      1

      1

      0

      0

      0

      0

      1776

      5

      Lathe

      1

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      1

      1

      8179

      1

      Milling

      0

      0

      1

      1

      1

      1

      1

      1

      0

      1

      1

      1

      1

      2031

      2

      Boring

      0

      0

      1

      1

      1

      0

      0

      1

      0

      1

      1

      1

      1

      1839

      4

      Welding

      0

      0

      0

      0

      1

      0

      0

      0

      0

      0

      0

      0

      1

      257

      6

      Grinding

      0

      0

      1

      1

      1

      0

      0

      1

      1

      1

      1

      1

      1

      1855

      3

      STEP 2

      Job

      Machine

      Nut

      Bol t

      Gear

      Hexagonal Gear

      Flange Pipe

      Screw

      Lead Screw

      Universal Coupling

      Lathe Centre

      Piston Connecting Rod

      Sprocket

      Tie Rod End

      Gear Pump Flange

      Lathe

      1

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      1

      Milling

      0

      0

      1

      1

      1

      1

      1

      1

      0

      1

      1

      1

      1

      Grinding

      0

      0

      1

      1

      1

      0

      0

      1

      1

      1

      1

      1

      1

      Boring

      0

      0

      1

      1

      1

      0

      0

      1

      0

      1

      1

      1

      1

      Shaper

      0

      0

      1

      1

      0

      1

      1

      1

      1

      0

      0

      0

      0

      Welding

      0

      0

      0

      0

      1

      0

      0

      0

      0

      0

      0

      0

      1

      Decimal Weight

      32

      32

      62

      62

      61

      50

      50

      62

      42

      28

      28

      60

      61

      Rank

      6

      6

      1

      1

      2

      4

      4

      1

      5

      7

      7

      3

      2

      STEP 3

      Job Machine

      Gea r

      Hexagona l Gear

      Universa l Coupling

      Gear Pump Flange

      Flang e Pipe

      Tie Ro d En d

      Scre w

      Lead Scre w

      Lathe Centr e

      Nu t

      Bol t

      Piston Connectin g Rod

      Sprocke t

      Decima l Weight

      Ran k

      Lathe

      1

      1

      1

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      8188

      1

      Milling

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      0

      1

      1

      8163

      2

      Grinding

      1

      1

      1

      1

      1

      1

      0

      0

      1

      0

      0

      1

      1

      8083

      3

      Boring

      1

      1

      1

      1

      1

      1

      0

      0

      0

      0

      0

      1

      1

      8067

      4

      Shaper

      1

      1

      1

      0

      0

      0

      1

      1

      1

      0

      0

      0

      0

      7280

      5

      Welding

      0

      0

      0

      1

      1

      0

      0

      0

      0

      0

      0

      0

      0

      768

      6

      STEP 4

      Job Machine

      Gear

      Hexagonal Gear

      Universal Coupling

      Gear Pump Flange

      Flange Pipe

      Tie Rod End

      Screw

      Lead Screw

      Lathe Centre

      Nu t

      Bol t

      Piston Connecting Rod

      Sprocket

      Lathe

      1

      1

      1

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      Milling

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      0

      1

      1

      Grinding

      1

      1

      1

      1

      1

      1

      0

      0

      1

      0

      0

      1

      1

      Boring

      1

      1

      1

      1

      1

      1

      0

      0

      0

      0

      0

      1

      1

      Shaper

      1

      1

      1

      0

      0

      0

      1

      1

      1

      0

      0

      0

      0

      Welding

      0

      0

      0

      1

      1

      0

      0

      0

      0

      0

      0

      0

      0

      Decimal

      Weight

      62

      62

      62

      61

      61

      60

      50

      50

      42

      32

      32

      28

      28

      Rank

      1

      1

      1

      2

      2

      3

      4

      4

      5

      6

      6

      7

      7

      CLUSTER 1

      Table 4 Cluster 1 based on calculated data

      Job Machine

      Gear

      Hexagonal Gear

      Universal Coupling

      Gear Pump Flange

      Flange Pipe

      Tie Rod End

      Screw

      Lead Screw

      Lathe Centre

      Nut

      Bol t

      Piston Connecting Rod

      Sprocket

      Lathe

      1

      1

      1

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      Milling

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      0

      1

      1

      Grinding

      1

      1

      1

      1

      1

      1

      0

      0

      1

      0

      0

      1

      1

      Boring

      1

      1

      1

      1

      1

      1

      0

      0

      0

      0

      0

      1

      1

      Shaper

      1

      1

      1

      0

      0

      0

      1

      1

      1

      0

      0

      0

      0

      Welding

      0

      0

      0

      1

      1

      0

      0

      0

      0

      0

      0

      0

      0

      CLUSTER 2

      Table 5 Cluster 2 based on calculated data

      Job

      Ma-

      chine

      Gear

      Hexagonal Gear

      Universal Coupling

      Gear Pump Flange

      Flange Pipe

      Tie Rod End

      Screw

      Lead Screw

      Lathe Centre

      Nut

      Bol t

      Piston Connectin g Rod

      Sprocket

      Lathe

      1

      1

      1

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      Milling

      1

      1

      1

      1

      1

      1

      1

      1

      0

      0

      0

      1

      1

      Grinding

      1

      1

      1

      1

      1

      1

      0

      0

      1

      0

      0

      1

      1

      Boring

      1

      1

      1

      1

      1

      1

      0

      0

      0

      0

      0

      1

      1

      Shaper

      1

      1

      1

      0

      0

      0

      1

      1

      1

      0

      0

      0

      0

      Welding

      0

      0

      0

      1

      1

      0

      0

      0

      0

      0

      0

      0

      0

      CELL LAYOUT

      Table 6 cell layout based on cluster arrangement

      CELL

      MACHINES

      JOBS

      Cell 1

      1,5

      3,4,5,8,12,13

      Cell 2

      2,3,4,6

      1,2,6,7,9,10,11

    2. MAKE SPAN CALCULATION Table 7 calculation of make span

      Job Machine

      Lathe

      Milling

      Grinding

      Boring

      Shaper

      Welding

      Time to complete

      the process (min)

      IN

      OUT

      IN

      OUT

      IN

      OUT

      IN

      OUT

      IN

      OUT

      IN

      OUT

      Gear

      0

      19

      19

      49

      49

      53

      53

      68

      68

      128

      128

      128

      128

      Hexagonal Gear

      0

      18

      18

      63

      63

      69

      69

      73

      73

      138

      138

      138

      138

      Universal Coupling

      0

      18

      18

      38

      38

      44

      44

      54

      54

      114

      114

      114

      114

      Gear Pump Flange

      0

      27

      27

      42

      42

      47

      47

      78

      78

      78

      78

      95

      95

      Flange Pipe

      0

      50

      50

      85

      85

      110

      110

      145

      145

      145

      145

      12

      172

      Tie Rod End

      0

      26

      26

      54

      54

      61

      61

      88

      88

      88

      88

      88

      88

      Screw

      0

      58

      58

      73

      73

      73

      73

      73

      73

      135

      135

      135

      135

      Lead Screw

      0

      35

      35

      55

      55

      55

      55

      55

      55

      115

      115

      115

      115

      Lathe Centre

      0

      30

      30

      30

      30

      35

      35

      35

      35

      98

      98

      98

      98

      Nut

      0

      17

      17

      17

      17

      17

      17

      17

      17

      17

      17

      17

      17

      Bolt

      0

      20

      20

      20

      20

      20

      20

      20

      20

      20

      20

      20

      20

      Piston Con- necting Rod

      0

      0

      0

      17

      17

      24

      24

      35

      35

      35

      35

      35

      35

      Sprocket

      0

      0

      0

      15

      15

      20

      20

      75

      75

      75

      75

      75

      75

      MAKE SPAN CALCULATION

      Table 8 processed makes span data

      78

      Job Machine

      Lathe

      Milling

      Grinding

      Boring

      Shaper

      Welding

      Time to com- plete the pro- cess (min)

      IN

      OUT

      IN

      OUT

      IN

      OUT

      IN

      OUT

      IN

      OUT

      IN

      OUT

      Nut

      0

      17

      17

      17

      17

      17

      17

      17

      17

      17

      17

      17

      17

      Bolt

      0

      20

      20

      20

      20

      20

      20

      20

      20

      20

      20

      20

      20

      Piston Connecting Rod

      0

      0

      0

      17

      17

      24

      24

      35

      35

      35

      35

      35

      35

      Sprocket

      0

      0

      0

      15

      15

      20

      20

      75

      75

      75

      75

      75

      75

      Tie Rod End

      0

      26

      26

      54

      54

      61

      61

      88

      88

      88

      88

      88

      88

      Gear Pump Flange

      0

      27

      27

      42

      42

      47

      47

      78

      78

      78

      95

      95

      Lathe Centre

      0

      30

      30

      30

      30

      35

      35

      35

      35

      98

      98

      98

      98

      Universal Coupling

      0

      18

      18

      38

      38

      44

      44

      54

      54

      114

      114

      114

      114

      Lead Screw

      0

      35

      35

      55

      55

      55

      55

      55

      55

      115

      115

      115

      115

      Gear

      0

      19

      19

      49

      49

      53

      53

      68

      68

      128

      128

      128

      128

      Screw

      0

      58

      58

      73

      73

      73

      73

      73

      73

      135

      135

      135

      135

      Hexagonal Gear

      0

      18

      18

      63

      63

      69

      69

      73

      73

      138

      138

      138

      138

      Flange Pipe

      0

      50

      50

      85

      85

      110

      110

      145

      145

      145

      145

      172

      172

    3. PENALTY COST CALCULATION

      The penalty cost for the every se- quence is calculated as per the following method.

      To make one component (Job No.3), the elapsed time is 128 min.

      For 100 components, it takes 100*128=12800 min

      For a day working hours (2 shift/day)=16hrs=16*60=960min

      To make 100 jobs, it will take 12800/960=13.3 days Due date to complete the job 3 is 10 days.

      Delay time is 3.3 days

      Penalty in Rs. Per day per part of job no.3 is Rs. 15. Therefore, Penalty=Rs. 4950.

      In similar fashion, the penalty for all the jobs is calculated. Total penalty for this job sequence f(x) =Rs. 38100.

    4. CONCLUSION

      The main aim of this project is to explore the potential of Scatter Search for optimization of job shop scheduling prob- lems in cellular manufacturing systems. The inherent weakness of many search procedures is that they often get trapped in a region around some local minima. Their ability to breakout of such entrapments and achieve better, ideally global minima, is based on their capacity to provide a suita- ble mixture of intensification and diversi- fication. Scatter search also provides uni- fying principles for joining solutions based on generalized path constructions and by utilizing strategic designs where other ap- proaches resort to randomization. This pro- ject has addressed the problem of optimiz- ing the scheduling of cellular manufactur- ing systems, which consist of different manufacturing cells with the objective of minimizing the penalty cost. The problem has been solved using Scatter Search method. Rank Order Clustering technique is used here for the formation of cells. The optimal sequence for scheduling of ma- chines and jobs are identified and provides better optimization of penalty cost.

    5. REFERENCE

  1. A.Gnanavel Babu, S.Dhivya, J. Jerald, A.Noorul Haq Simultaneous Schedul- ing of Machines and Automated Guid- ed Vehicles in FMS using Scatter Search.

  2. Ang D.S., (1998a), Identification of part families and bottleneck parts in cellular manufacturing, Industrial management and data systems, 1, No. 2, pp. 3-7.

  3. Black J.T., (1991), "The design of the factory with a future", McGraw-Hill inc., New York.

  4. Chow W.S. and Hawaleskha O., (1992) An efficient Algorithm for solving machine chaining problem in cellular, computers and industrial engineering, 22, No. 1, pp. 95-100.

  5. El-Ghazali Talbi, "Metaheuristics from design to implementation", Pub- lished Inc., Hoboken, New Jersey, Published simultaneously in Canada, 2009

  6. Fred Glover and Manuel Laguna and Rafael Marti, Scatter search and path relinking: advances and applications", CO 80309-0419, USA.

  7. Glover, F., M. Laguna and R. Martí (2000), Fundamentals of Scatter Search and Path Relinking Control

  8. and Cybernetics, 29 (3), pp. 653-684

    http://leeds.colorado.edu/Faculty/Lagu na/articles/ss3.pdf (Last Access: March 24th 2003).

  9. Goldratt E.M.and cox J., (1986). "The Goal: A process of ongoing improve- ment", North River press, croton-on Hudson, New York.

  10. Harris, Jason and S. Coe, (2005), In- troduction to Scatter Search, Lecture handout: Paper Review, University of Guelph, Guelph.

  11. J. Christopher Beck and Nic Wilson, Proactive algorithms for job shop scheduling with probabilistic dura- tions", Journal of Artificial Intelli- gence Research 28 (2007) 183232, 2007.

Leave a Reply

Your email address will not be published. Required fields are marked *