Studies on Metaheuristics for m-Machines Scheduling Problem with Forbidden Zones

Studies on Metaheuristics for m-Machines Scheduling Problem with Forbidden Zones

M. Nur, Awaludin Fitra, Maruli H.

Graduate School of Mathematics, University Sumatera Utara, Medan, Indonesia

Abstract In machine scheduling of manufacturing systems there may be a certain time interval, during which jobs may not be continued. This research discuss a metaheuristic model of machine scheduling problem on d identical machine by considering a time interval of forbidden zones. This research represents a feasible or optimal scheduling of jobs by considering any time interval in forbidden zones. The model that formulated into linear programming with objective is minimized the completion time (makespan) in order to obtain time interval minimum in forbidden zones that represents by integer programming.

Keywords machine scheduling, forbidden zones, jobshop, linear programming.

1. INTRODUCTION

   Scheduling is the allocation of shared resources over- time to competing activities. Chaudhuri [1] showed that in some situations, it may be necessary to instantly inform that there are some certain rules that influence the decision making process, then the process added a constraint of time, the limited time of jobs or total makespan into the model. In manufacturing systems, there are also instances when accurate information about processes is not available or optimization methods are so complex and make it undesirable for decision makers to implement them. Abdekhodaee and Ernst [2] suggested the motivation for

   considering scheduling with starting time windows that

   Khammuang et al. [4] was extended that forbidden zones was presented as time interval during which a job cannot be started but can be processed. Furthermore, if a job is completed before the end of a time interval in forbidden zone, it will be released at the start of the next interval. Thus, the latest of a job may commence in Ij at t = 2j-1. The objective of the model is to sequence the jobs so that the number of intervals used is minimized.

   In this paper focus on a metaheuristic model with the aim is to minimize the makespan by considering the time interval in forbidden zones for m total of machine (m- machine) scheduling. We then represented into a linear programming model which the constraint of the scheduling is represented as an integer programming. This paper unfolds as follows. Section II we review some background information that adopted the scheduling problem with forbidden zones of time interval. Section III we present our model of d-machine scheduling with forbidden zones and then present the result in a given data in Section IV. Finally, conclusion and future research in the last section.

2. SCHEDULING PROBLEM WITH FORBIDDEN ZONES

   1. Definition of Machine Scheduling

      Assume that a given bipartite complete graph

      complements are forbidden zones. It represent a time

      G (V1 V2 ,V1 V2 )

      with

      V1 {v1,, vn} and

      intervals during which a job cannot be started, but can be processed. The model was based on a supply chain problem on a certain activity that was not allowed to commence inside in a particular time intervals.

      Given some definitions and results from an earlier

      V2 {w1,, wn} where n m . For each arc (vi , wj ) , there

      exist a real number, cij . Then, it determined an one-to-one mapping :V1 V2 which is the scheduling problem with objective function

      complementary paper [3]. Denote that n jobs to be scheduled by J1,,Jn. Let pi be the processing time of Ji where pi 1,i with partition time into a set of a butting

      min

      c ( )

      vV1

      intervals I {I1, I2 ,, Is } with I1 [0, 2] , I2 [2, 4] ,

      This scheduling problem can be represented by a matrix

      and Is [2s, 2, 2s] . Each Ij includes a corresponding

      n m,C cij and formulated as a linear programming with

      forbidden zone

      forbidden zone is

      Fj I j ,j , where it denoted that

      F1 (1, 2], F2 (3, 4]Fs (2s 1, 2s] .

      variable 0-1 of xij

      n m

      as a decision process, is

      We call I

      j \ Fj is the allowed zones.

      min

      cij xij

      i1 j 1

      (2.1)

      s.t

      m

      xij 1;

      j 1

      n

      xij 1;

      i1

      i 1,, n

      j 1,, m

      (2.2)

      (2.3)

      approximation of the Pareto frontier then Lei [10] extended the method by using a particle swarm optimization for multi-objective job-shop scheduling problem. The objective is to simultaneously minimize the makespan and total tardiness of the jobs.

      xij {0,1}; i 1,, n; j 1,, m

      (2.4)

   2. Machine Scheduling with Forbidden Zones

   with

   xij 1

   if and only if vi

   paired to

   w j . For each

   Assume m available machines,

   M j ( j 1,, m) , that

   constraint (2.2 2.4), each vi V1 paired to each element

   used to process n available jobs, Ji (i 1,, n) . Studied on

   of V2 and each wj V2 have at least an available feasible scheduling.

   Scheduling problems in their simple static and deterministic forms are extremely simple to describe and formulate, but are difficult to solve because they involve complex combinatorial optimization. For example, if n jobs are to be performed on m machines, there are potentially

   scheduling problem formulated each available jobs that allocated to a certain time intervals or a certain available machines. This scheduling problem can be represented by using Gantt chart as follows.

   (n!)m

   sequences, although many of these may be

   infeasible due to various constraints. In this paper, we focused on machine scheduling in job-shop scheduling context which there are m machines and n jobs to be processed. Each job requires m operations, one on each machine, in a specific order, but the order can be different for each job. Any given machine may observe new jobs arriving from outside the shop and from other machines within the shop. Udo [5] reports a simulation study that investigates a dynamic approach to scheduling jobs in a multi-machine job-shop. The shop performance evaluated based on three measures: mean job lateness, percentage of tardy jobs and lateness variance. The results indicate that using the cumulative distribution function of workload information can yield a better performance than using a proportional function of workload information or ignoring shop congestion information. Toker [6] consider the job- shop scheduling problem under a discrete non-renewable resource constraint under assumption that jobs have arbitrary processing times and resource requirements and there is a unit supply of the resource at each time period and develop an approximation algorithm for this problem in finding the makespan schedules. Gao et al. [7] addresses the flowtime job-shop problem (FJSP) with three objectives: minimize the makespan, minimize the maximum machine workload and minimize total workload and develop a new Genetic Algorithm hybridized with an innovative local search procedure (bottleneck shifting) for

   Fig. 1: Machines oriented of available jobs (Gantt chart)

   Fig. 2: Jobs oriented of available machines (Gantt chart)

   Based on both of the Gantt chart, the objective of scheduling problem is to determine the feasible scheduling by considering the oriented problem, total of available machines or total of available jobs as a constraint of the scheduling. Generally, scheduling problem can be classified and denoted by | | | where is total of available machines, is characteristic of a certain job and

   is characteristics of optimality problem [4].

   Megow et al. [11] proposed an extended stochastic scheduling models in determine a new on-line stochastic scheduling models. The objective of the models is to minimize the expected time of makespan, E wj C j . In

   the problem. this model was assumed that the time process of

   distribution, Pj , are independent, w j

   is the weight of the

   Cheng [8] studied the problem of scheduling n

   deteriorating jobs on m identical parallel machines where

   available jobs and

   C j as its completion time. Thus, it

   for each jobs processing time is a nondecreasing function on its start time. The objective of the model is to determine

   obtained that rj rk for j k

   where Ji (i 1,, n) is a

   an optimal combination of the due-date and schedule so as

   set of available jobs with

   rj denoted as time process of

   to minimize the sum of the due-date, earliness and tardiness penalties and showed this problem is NP-hard. Also, present a heuristic algorithm to find near-optimal solutions for the problem. Vilcot [9] minimize the makespan and the maximum lateness, and interested in finding an

   makespan for each jobs j. In this scheduling, given a specification of jobs of time decision with starting time t and t for the next interval time process. Set S j and C j as a

   random variable of starting time and time process of

   available jobs, respectively. Thus, the model was formulated by

   n

   (xij yij ) 1; i

   i1

   n

   (3.3)

   E w C

   w E C

   yij 1; j

   (3.4)

   jJ

   j j

   jJ

   j j

   i1

   xij , yij {0,1}

   Billaut and Sourd [12] proposed a new scheme on forbidden zones of scheduling problem. It given a set of available jobs J {J1,, Jn} to be scheduled on a single

   where

   xij

   1; if job i start and release at Rj \ Fj

   machine with a processing time p j for each jobs. Denote

   0; otherwise

   that the jobs start at integral time points which some of it contains or defined as forbidden. Then, denote that

   y 1; if job i start at Rj and finish at Fj

   F {F1,, FK } is the set of K forbidden start times

   ij

   0; otherwise

   without loss of generality where 0 F1 F2 Fk . The

   objective of this model is to schedule the jobs so that no jobs start at a forbidden start time and also minimize the makespan of the scheduling. Given the start time S1,, Sn where the forbidden start time is defined by

   shows a decision making process if a unit job is allow to start and release in a certain time interval which is contains a forbidden zones of a given processing time. The objective function (3.1) that we wish to minimize the makespan of the machine scheduling. Constraint (3.2) ensures that

   S j F,1 j n

   processing time of machine k, pk , is less or equal to pi .

3. THE MODELS

   In this paper we use the illustration of scheduling problem with forbidden zones by Khammuang et al. [4] as follows.

   Fig. 1: Illustration of time interval as forbidden zones

   Assume that we have n available jobs that to be scheduled, J {J1,, Jn} with pi 1 as processing time for each jobs. This available jobs need different resource types of machine, numbered m 1,, d while being processed.

   The decision making process of all units jobs scheduling is equal to 1 on constraint (3.3). Constraint (3.4) ensures the models that at most one job can be processed in a forbidden zones.

4. CONCLUSIONS

In complex optimization problem there is some conditions that influences the processing time of unit jobs, especially in machine scheduling problem. Mathematically, this problem can be solved by using a decision variable or decision making process method. This paper studied the scheduling problem in m-machines with a metaheuristic assumption models which contains interval time as a constraint that defined as a forbidden zones. Our model presented in a linear programming with objective function is to minimize the makespan of the scheduling. Thus, we wish to determine the minimum interval time in forbidden zones due to the decision making process for both of each unit jobs and machines.

Then assume that we have a partition processing time in

machine scheduling,

R {R1,, Rs } , with interval time of

forbidden zones

Fj for each

Ri (i 1,, n) . A scheduling

of subset J of unit jobs is feasible if and only if all of unit jobs in J start or at release time and compeleted before or after limit time based on the partition processing time. Our model ensure that the available jobs is scheduled one-by- one. Thus, we can formulated the model as follows.

min

n

t j j 1

(3.1)

s.t

d

pk pi

jJ m1

(3.2)

REFERENCES

1. Chaudhuri, S. Introduction to the scheduling problem, IEEE Design & Test of Computers, Vol. 5 (1995), pp. 60-69.

2. Abdekhodaee, A. and Ernst, A.T. Scheduling jobs with forbidden zones in the context of coal supply chain, Proceedings of European Operations Management Association 2004 Operations Management as a Change Event, (2004b), INSEAD, pp. 669-676.

3. Abdekhodaee, A. and Ernst, A.T. Scheduling jobs with forbidden zones, Technical report, Commonwealth Scientific and Industrial Research Organisation, (2004a).

4. Khammuang, K., Abdekhodaee, A., and Wirth, A. On-line scheduling with forbidden zones. Journal of the Operational Research Society, Vol. 58 (2007), pp. 80-90.

5. Udo, G.J. A simulation study of due-date assignment rules in a dynamic job-shop, Journal of the Operational Research Society, Vol. 45 (1994), pp. 1425-1435.

6. Toker, A., Kondakci, S., Erkip, N. Job-shop scheduling under a non- renewable resource constraint, Journal of the Operational Research Society, Vol. 45 (1994), pp. 942-947.

7. Gao, J., Gen, M., Sun, L., and Zhao, X. A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job- shop scheduling problems, Computers & Industrial Engineering, Vol. 53 (2007), pp. 149-162.

8. Cheng, T.C.E., Kang, L.Y., and Ng., C.T. Due-date assignment and parallel-machine scheduling with deteriorating jobs, Journal of the Operational Research Society, Vol. 58 (2007), pp. 1103-1108.

9. Vilcot, G., and Jean, B. A tabu search and a genetic algorithm for solving a bicteria general job-shop scheduling problem, European Journal of Operational Research, Vol. 190 (2008), pp. 398-411.

10. Lei, D. A Pareto archive particle swarm optimization for multi- objective job-shop scheduling, Computers & Industrial Engineering, Vol. 54 (2008), pp. 960-971.

11. Megow, N., Uetz, M., and Vredeveld, T. Models and algorithms for stochastic online scheduling, Math. Operational Research, Vol. 31 (2006), pp. 513-525.

12. Billaut, J.C. and Sourd, F. Single machine scheduling with forbidden start times. Lecture notes on Universite Pierre et Marie Curie, Vol. 17 (2001), pp. 307-329.