Optimization of Job Shop Scheduling Problems in Cellular Manufacturing Systems

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.