For verification of this paper, please visit on http://www.socialresearchfoundation.com/resonance.php#8

There are many literature and research papers that deals with the single machine scheduling problems. The proposed paper proposes a single machine multi-objective scheduling problem. This problem has two objectives the first one is, to schedule the system which deliver the output with minimum difference between due dates and actual processing time, and second one is to optimize the profit or loss for the machine. Scheduling models concerns with the determination of an optimize time. A set of services perform on a single machine is a tedious job to operate. Every job has its due dates and lateness penalty/loss variation. We have to manage jobs for minimizing loss and consider due date delivery. In the present chapter we have considered multi-objective scheduling problem with fuzzy parameters. We know that practically completion time for a job is not fixed or certain. There is always a variation or uncertainty in time management. In the present problem we have considered due date time and processing time in the form of triangular fuzzy number. Although, many ranking methods have been proposed and described by researchers, however there is yet no technique that can always give satisfactory result for every situation. For overcome these problems in the present work we have used ranking method proposed by Ching at al. and to comparison fuzzy numbers we have used algorithm developed by Tzung-Pei Hong, which was used by many researchers and justify this ranking technique by giving better results.

There are many literature and research papers that deals with the single machine scheduling problems. The proposed paper proposes a single machine multi-objective scheduling problem. This problem has two objectives the first one is, to schedule the system which deliver the output with minimum difference between due dates and actual processing time, and second one is to optimize the profit or loss for the machine. Senthikumar et al. introduce a survey of literature for single machine scheduling problems in three category- Offline scheduling, Online scheduling, Miscellaneous Scheduling. Baker et al. develop sequences with earliness and tardiness penalties under just-in-time production Recently many researchers have proposed different models for distinct situations Biskup et al., Weerdt et al., Xin Li, , SE Jayanthi et al, CJ Liao.et al. , Tzung , Jinwei Gu,Manzhan and others.

Problem Formulation

In this problem we have proposed a model to solve single machine multi-objective scheduling problem under uncertainty, which has been described by triangular fuzzy numbers.

Suppose there are  n-jobs  available at time 0 and these jobs are to be processed on a single machine. Denote by a constant  the time needed to process job  if no breakdown occurs during its processing. Due to the breakdowns, the actual time needed to process job  may be more than , and the time may vary in different processing orders. It is assumed that the machine could process one and only one job at a time, and once a job begins to be processed on the machine, it could not be pre-empted by other jobs (except by machine breakdowns) until its completion. There are a lot of real life problems that are similar to single machine scheduling problem. A real time example is the laundry services where orders from customers arrive early in the morning, and due dates are determined at the pick-up times, and pick-ups are made by customer itself. Whenever the due date or pick-up time has missed, a special delivery services can be required by the laundry operator, the cost of which is totally bear by laundry management i.e the tardiness of job.

In the present problem we have taken due dates in fuzzy time duration for the flexibility. Since there are many factors that job not completed in time. Therefore for a limited flexibility customer and service provider shall be relaxed. The processing time for the job on machine also taken in flexible manner in the form of fuzzy number. So the problem is to find the optimize order or schedule in which n-job have to be processed with minimum mode of difference of earliness and tardiness time or cost.

So the present single machine problem with common due date can be formulated as follows:-

1. We have  n-jobs that have to be processed on single machine.

2. The processing time of job i shall be t_i, for i=1,2,3,…n. and the t_i, is given in the form of triangular fuzzy number.

t_i = (t_i ^a, t_i ^b, t_i^c)

3. We assumed that all jobs are available in time and ready to process at time zero.

4. One job will be process on the machine, at a time.

5. Each job has its due time D_i and C_i be the completion time of the job i.

D_i = (D_i ^a, D_i ^b, D_i^c) and C_i = (C_i ^a, C_i ^b, C_i^c)

6. If a job i is completed before the due time then its earliness E_i can be formulize as E_i = D_i – C_i.

7. If a job i is completed after due time  then its tardiness time T_i is given by E_i = C_{i –} D_{i .}

8. There is a reward and penalty for each job depends on its completion time.

9. Reward for job i is r with unit time and penalty for job i is p with unit time.

10. All the arithmetic calculation with fuzzy number are done on standard operations (Max-Min) defined by TP Hong such as addition, subtraction or difference and comparison on triangular fuzzy numbers.

11. We have supposed that due time is less than the total processing time of all n-jobs.

The problem can be formulated mathematically as:

Example:

Let we have three jobs {J₁, J₂, J₃} with fuzzy processing time on a single machine { t₁, t₂, t₃}and due dates for these jobs be {D₁, D₂, D₃} and the common due date will be D = D₁ + D₂ + D₃.

Reward for job i is r=1 with unit time and penalty for job i is p=2 with unit time

For the three jobs we have all possible schedule 3! Or 6.

Let S = {S₁ , S₂ , S₃ , S₄ , S₅ , S₆}

where    S₁ = { J₁ ,J₂ ,J₃}, S₂ ={ J₁ ,J₃ ,J₂},  S₃ = { J₂ ,J₁ ,J₃},  S₄ = { J₂ ,J₃ ,J₁},  S₅ = { J₃ ,J₁ ,J₂},  S₆ = { J₃ ,J₂ ,J₁}

 

 

 

 

 

 

 

So the value of F for the schedule {S₁ , S₂ , S₃ , S₄ , S₅ , S₆} is {-8.163, -23.145, -10.563, -30.127, -30.178,  -33.968}. The minimum value of F is on -8.163 for the schedule S₁ = {J₁ , J₂ , J₃}. Hence the optimum schedule and completion time is as follows:

 

 

Hence the Completion time for the schedule S₁ is (13, 16, 21) and due time loss is 8.163 unit. Since job has been completed after due date therefore service provider faces a loss.

From the example we have observed that –

1.     The optimal schedule appears depends on t_i, D_i, C_i, r_i & p_i.

2.     There are n! schedule option for n-jobs. So, if we consider 10 job schedule problem then we have all over 10! =3628800 possible schedules, which are not feasible to calculate manually.

Proposed Algorithm:

Problem Statement: We have n-jobs to be processed on a single machine. The processing time of these jobs J_i (I = 1,2,3….n) with processing time t_i (I = 1, 2, 3, …n). It is pre-assumed that all the jobs are ready to processed at initial time zero with due dates D_i (deadline), after this deadline a reward r_i or penalty p_i be applied on unit time. The problem is to search an optimal schedule as to minimize sum of earliness and tardiness costs (profit and loss).

Step 1: Sort the n-jobs in non-decreasing order of processing time t_i such that- t₁ £ t₂ £ t₃ £ t₄ £ t₅ ….. £  t_n corresponding jobs J_1, J₂, J₃, ….. J_n.

Then evaluate

. T = t₁ + t₂ + t₃ + t₄ + t₅ ….. +  t_n & D = D₁ + D₂ + D₃ + … +D_n

Initiate T₀ =  t₁ & E₀ = D₁

Introduce non empty set of schedule job S^E₀ = f , S^T₀ = f

. Step 2: Consider job J₁ with minimum processing time t₁.

. Set T₁ = T₀ =  t₁ & E₁ = E₀ = D₁

. Check weather T₁ < E₁ if so then set S^E₁ =  S^E₀ È { J₁ } and S^T₁ = S^T₀

. Check weather T₁ > E₁ if so then set S^T₁ =  S^T₀ È { J₁ } and S^E₁ = S^E₀

Step 3: Consider job J_i with minimum processing time t_i. such that neither J_i Ï S^T_i-1 nor J_i Ï S^E_i-1 and  J_i-1 Î S^T_i-1 or  J_i-1 Î S^E_i-1.

. Set T_i  =  T₁ + T₂ + …+ T_i-1 & E_i = E₁ + E₂ +…..+E_i-1

. Check weather T_i < E_i if so then set S^E_i =  S^E_i-1 È { J_i } and S^T_i = S^T_i-1

. Check weather T_i > E_i if so then set S^T_i =  S^T_i-1 È { J_i } and S^E_i = S^E_i-1

  The above process will continue till all the jobs set { J_1, J₂, J₃, ….. J_n.} Í S^E_n È  S^T_n .

So, we have seen that the above proposed algorithm involves only n-iteration as compared to n! possible schedule calculations.

Fuzzy Scheduling.

Based on Algorithm proposed

Reduced number of iteration.

1. Baker K.R. and Scudder G.D. (1990), ‘Sequencing with earliness and tardiness penalties: A review’, Operation Research, 38(1), pp. 22-36. 2. Biskup, D. and Feldmann, M. (2001). Benchmarks for scheduling on a single-machine restrictive and unrestrictive common due dates. Computers and Operations Research, 28(8): 787 – 801. 3. Jinwei Gu,Manzhan Gu,and Xingsheng Gu (2014), Optimal Rules for Single Machine Scheduling with Stochastic Breakdowns, Recent Advances on Modelling, Control, and Optimization for Complex Engineering Systems, Volume 2014 |Article ID 260415 | https://doi.org/10.1155/2014/260415 4. Kumar P et al (2019) “Uncertainty Involved in Job - Shop Scheduling'' published in ‘Remarking An Analisation’ , VOL-3* ISSUE-11*(Part-1) February 2019, pg 7-11 E: ISSN NO.: 2455-0817; Impact factor SIJF 5.879. 5. Kumar P et al (2019), “ A study of thermally induced vibrations of circular plate of non-uniform thickness” in the International conference on Intelligent computing & smart communication”, organised by THDC-IHET Tehri Uttarakhand and SoE, Cochin University of science & technology Cochin Kerala from 19-21 April 2019. 6. Kumar P et al (2019), “Calculation of the Replacement Time for the Fuzzy Replacement Problem using Fuzzy Ranking Method'' published in ‘Shrinkhla Ek Shodhparak Vaicharik Patrika’ , VOL-6 * ISSUE-6 * (Part-1) February- 2019, pg 167-172, E: ISSN NO.: 2349-980X; Impact factor SJIF 5.689. 7. Kumar P, (2017) “The Generalized Fuzzy Demand and Supply Transportation Problem”, published in Research Journal of Recent Sciences ISSN 2277-2502, vol. 6(8), 12-16, Aug 2017. 8. Liao, C.J. and Cheng, C.C. (2007). A variable neighbourhood search for minimizing single machine weighted earliness and tardiness with common due date. Computers and Industrial Engineering, 52(4): 404 – 413. 9. Senthilkumar P., Sockalingam Narayanan (2010), Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines, Intelligent Information . Management. 10. Tzung-Pei Hong, Tzung-Nan Chuang (1999), ‘A new triangular fuzzy Johnson algorithm’, v-36 Computer & Industrial Engineering, pp 179-200. 11. Mohamad N.H & Said F. (2011), ‘Solving single machine scheduling problem with common due date’, Business Management Dynamics, vol. 1(4), pp.63-72. 12. Weerdt Md, Baart R & Lei He (2021), ‘Single-machine scheduling with release times, deadlines, setup times’, European Journal of Operation Research, v-291, pp. 629-639. 13. Cheng T.C.E., Kang L., Ng C.T. (2004), ‘Due date assignment and single machine scheduling with deteriorating jobs’, Journal of the operation Research Society, 55(2), pp. 198-203. 14. Jayanthi, S.E. and Anusuya, S., Minimization of Total Weighted Earliness and Tardiness using PSO for One Machine Scheduling, Vol.10(1), 2017, pp.35-44. 15. Weerdt, M.D., Baart, R. & He, L., Single Machine Scheduling with release times, deadlines, setup times and rejection, European Journal of Operational Reseach, 291, 2021, pp. 629-639. 16. Li, Xin, Ventura, J.A., Exact Algorithms for a joint order acceptance and scheduling problem, International Journal of Production Economics, vol. 223(2020), id.-107516.