Multi-Objective Flexible Job Shop Scheduling Optimization Models (I)
Elena Simona Nicoară
Petroleum-Gas University of Ploieşti, Information Technology, Mathematics and Physics Department, Bucureşti Blvd., 39, Ploieşti, 100680, Romania
e-mail: snicoara77 @yahoo.com
Abstract
In manufacturing area, the most difficult problems related to the time-efficiency frequently occur if the jobs to be scheduled are heterogeneous, if there are alternative routes on the machines for the jobs and multiple objectives are imposed. This framework, named Multi-Objective Flexible Job Shop Scheduling Problems (MOFJSSP), has been formalized, modeled and studied in the last decades from many perspectives in order to capture all the influential factors and to optimally solve the multi-objective problem while satisfying the multiple specific constraints. The author focused the research on the various optimization models adequate for the (MOF)JSSP, both conventional and non-conventional: Petri nets, waiting systems, general decision models, logical formulations as STRIPS language, Markov processes, Monte Carlo simulation and procedural models (agent-based models, evolutionary algorithms, expert systems, fuzzy techniques, neural networks). The structure, classification and analysis of the optimization models is extensively new, as the MOFJSSP models were less reported in the literature than the JSSP models. All the models are analyzed in the research (which is divided into two parts), in general case and for a specific real JSS process in drugs industry based on over 600 tasks to be optimally scheduled. The conclusions in this first part of the study reveal the complexity of MOFJSSP and the analysis outcome of two optimization models for MOFJSSP: waiting systems and STRIPS language. The results of the research (part I and II) point out the limits or critical aspects of all the mentioned optimization models and the process characteristics that claim certain model as the most adequate.
Key words: flexible job shop scheduling, optimization model, time-efficiency, multi-objective JEL Classification: C61, L65
Introduction
Nowadays, many manufacturing companies, regardless of dimension, take an intensive use of Enterprise Resource Planning (ERP) systems, the reason being the beneficial role of information technology in management at all the levels. These information systems, trying to satisfy the general performance objectives - quality, efficiency and security - on a limited resources background, have a global perspective over the enterprise. However, in every department, specialized tools operate to contribute to the general objectives and also to ensure an adequate relationship with the decision tools in other departments. The present study focuses on the scheduling department, where the specific performance refers to time. Setting the manufacturing schedules such that a minimum time is necessary to complete all the jobs in a certain time horizon is one of the main components in almost every ERP system.
One of the not-easy-to-handle production systems is based on manufacturing a range of product types, not a single type, on a set of machines, following certain formulas. For every industry specific time horizon, a number of batches named jobs (of all types), must be efficient scheduled in the job shop. The jobs are heterogeneous and consequently frequent changes on the manufacture equipment and frequent changes for the operational sequences occur. This kind of production system is specific to many industries, such as: pharmaceuticals, chemicals, food industry, furniture, electronic devices and so on.
The vast theoretical and practical background (Brucker and Schlie, 1990; Applegate and Cook, 1991; Jain and Meeran, 1999) of this manufacture condition is grouped around the concept of Job Shop Scheduling Problems (JSSP). In short, a JSSP states that a finite set of heterogeneous jobs formed by many operations have to be optimally scheduled on a set of finite machines such that the precedence constraint, the non-preemption constraint and the resource capacity constraint are satisfied. The main objective is to obtain a minimum makespan for the set of jobs, characterized by some attributes as: ready time, processing time on resource, due date, priority etc. The resources, on the other hand, can be energetic, human labor type, machine and so on and certain attributes also for them are set. Note that in the theoretical formulation, all the resources are considered machines. An optimal schedule is the output of the JSSP; it is a time-optimal allocation of the limited resources to the operations.
The scheduling process becomes more difficult when the routings of the jobs on the resources are flexible and multiple objectives must be simultaneously satisfied, for example: minimize lateness, maximize workload, minimize jobs flow time, minimize work-in-process, minimize cost to set the machines, maximize total workload on the machines. All these manufacturing circumstances frame the problem in the multi-objective flexible JSSP (MOFJSSP) category. The mathematical formulation for MOFJSSP is presented in the next section, together with a case study in drugs industry.
For this kind of economic process, various optimization models are available: Petri nets, waiting systems, general decision models, logical formulations such as STRIPS language, Markov processes, Monte Carlo simulation, agent-based models, evolutionary algorithms, expert systems, fuzzy techniques and neural networks. As a precise division of the models in strictly descriptive ones and strictly normative ones could not be done, all of them have descriptive and normative attributes. In the third section of the paper an analysis of these models is started, in order to settle the models limits and advantages and to observe the particular characteristics of the manufacture processes that require certain model as the most adequate. In this first part of the research two models are analyzed, waiting systems and STRIPS language, and in part II the other models are to be dissected.
Multi-Objective Flexible Job Shop Scheduling Problem
Less formally, a job shop scheduling process consists in computing an optimal sequence that the jobs in a production plan must be put on work on the machines. The jobs are formed by many operations, for every job we know the routing on the machines and the corresponding processing times and the explicit order for the operations of the jobs. We seek a minimum makespan schedule for the jobs, while satisfying three cumulative constraints.
The mathematical formulation for this kind of hard scheduling problem was extended (Nicoară et al., 2011) from the deterministic predictive JSSP (Brucker and Schlie, 1990) to include the type II flexibility, where alternative routings for the jobs are allowed. In the mathematical model of Flexible Job Shop Scheduling Problem (FJSSP) described below (Nicoară et al., 2011) the natural assumptions are used: a) the jobs ready times are set to 0, b) all the machines are available at time 0, c) the number of machines and jobs are finite and constant in time, d) the processing times of the
operations are finite and constant, and e) the probability for machine breakdowns and the setup times are statistically included in the processing times.
The input data of FJSSP are:
o a finite set M of m (m ∈ Z) machines, where Z is the set of integers;
o a finite set J of jobs, each job i∈J consisting in an ordered sequence of ni operations,
i j
i j n
o, , =1, ;
o for each operation oi,j (i∈J, j=1,ni), the set of machines which can perform it, MAi,j ⊆M, with card(MAi,j)≥1, where card(MAi,j) is the cardinality of the set MAi,j , and the processing times τik,j∈Z , k∈MAi,j are given.
Therefore, to each operation, oi,j, one can associate a set Di,j of processing times:
} ,
, 1 ,
{ , ,
, i ij
k j i j
i Z i J j n k MA
D = τ ∈ ∈ = ∈
. (1)
A solution is a valid schedule for J , defined as a collection of machine schedules as in:
m k Z n j J i MA k o
sk :{ i,j ∈ i,j, ∈ , =1, i}→ , =1, , (2)
which satisfies the constraints associated to the process (Jain and Meeran, 1999):
o the precedence constraint: for two consecutive operations of a job, the successor operation must be processed only after the first one ended;
o the non-preemption constraint: an operation, once started, can not be interrupted to be continued later;
o the resource capacity constraint: a machine processes one and only one operation at a time and an operation is processed by at most a machine at a time.
An overall schedule is S={sk k=1,m}, where all the operations performed on all the machines m
k =1, are scheduled.
The uni-objective (F)JSSP solution is the overall schedule, S, which consists in all the operations of all the jobs on the machines, ordered by the positive integer values of the functions sk,k=1,m. To this schedule a performance measure, Cmax(S), is assigned to be minimised:
) ) ( ( max
)
( , 1, , 1, , ,
max S i J j nk m sk oini ini
C = ∈ = i = +τ . (3)
The relation (3) computes the makespan as the maximum end time, considering all the operations in the schedule.
The objective is to minimize the performance measure, which indicates, from the temporal constraints point of view, how well the scheduling is handled. More precisely, the primary objective consists in minimization of the makespan:
)) ( ( min
)
( { _ } max
*
max S C S
C = S∈feasible schedules . (4)
A schedule with minimum makespan is named optimal solution of the (F)JSSP.
For the multi-objective FJSSP (MOFJSSP), additional objectives to the makespan are considered, as we mentioned above.
A MOFJSSP Case Study in Drugs Industry
In drugs industry, most of the scheduling systems are MOFJSSP-type. The case study covers such a manufacturing process, where 16 different types of pellets drugs are produced (see table 1), using some flexible routes, on 20 machines (see figure 1 and table 2) (Nicoară, 2011).
In figure 1 the technological sequences of operations on the machines is provided.
Fig. 1. The primal technological sequences of operations on the machines (Nicoară, 2011) In the MOFJSSP formulation, every batch in every type of drug corresponds to a job, and the production phases to complete a batch correspond to operations of that job.
The considered process instance is an average dimension instance: 79 jobs for a scheduling horizon of one month, according to table 1. The input data in table 2 indicate a total number of 606 operations to be scheduled.
Table 1. Product types distribution on batches
Poduct type No.
batches
Batches index
1 (Analgin) 8 1..8
2 (Antacid) 1 9
3 (Ascovit 100) 13 10..22
4 (Ascovit 200) 4 23..26
5 (Ascovit 60) 3 27..29
6 (Biseptrim cl.) 1 30
7 (Biseptrim) 19 31..49
8 (Ephimigrin) 1 0
Poduct type No.
batches
Batches index 9 (Europirin T) 3 51..53
10 (Europirin) 3 54..56
11 (Eurosept) 4 57..60
12 (Paracetamol Pus) 2 61..62 13 (Paracetamol
Sinus) 11 63..73
14 (Paracetamol) 3 74..76 15 (Tussin Forte) 2 77..78
16 (Tussin) 1 79
An example of feasible schedule for the 606 operations may be the sequence of pairs (i,j):
(6,1)(76,1)(53,1) ... (69,3) ... (54,8)(60,8)
ordered by the start times associated to the operations, where i is a job in J and j is an operation in the job i. The detailed description of the schedule is in table 3.
5, 6, 7, 8 Compress 1 Supply,
i h 2 Blend 3 Granulate 4 Dry up
18 Pack blisters in boxes 1 9 Semi-automatic
divide
10 Automatic divide
11 Blister packGultig
14 Attach top container
17 Print box 2 20 Collective pack
15 Label bottle 16Print box1
13 Blister
pack IMA 12 Blister packGultig2
19 Pack blisters in boxes 2
Table 2. Input data for the drug industry instance Routings of the jobs on the machines
Machine / machines Product
type No.
jobs No.
op. Processing times (minutes)
1 2 7 11,13 18 20
1 8 6
5 10 476 200,167 800 113
1 2 3 4 8 9,10 14 15 17 20
2 1 10
5 15 20 30 320 685,342 394 137 253 120
1 2 5,6 9,10 14 15 17 20
3 13 8
5 20 150,206 325,313 684 214 341 188
1 2 5,7 12 18 16 20
4 4 7
5 20 120,222 133 500 300 75
1 2 7 9,10 14 15 17 20
5 3 8
5 20 315 263,225 560 150 239 132
1 2 5,6 12 19 16 20
6 1 7
5 10 83,105 67 250 84 38
1 2 5,6 12 18 16 20
7 19 7
5 10 83,105 67 108 84 38
1 2 3 4 5,7 13 18 16 20
8 1 9
5 10 10 20 120,159 200 400 150 38
1 2 7 11,13 18 20
9 3 6
5 10 360 286,222 800 150
1 2 3 4 7 11,13 18 20
10 3 8
5 10 355 120 65 357,278 700 188
1 2 3 4 8 9,10 14 15 17 20
11 4 10
5 20 45 30 554 605,510 567 172 316 150
1 2 3 4 5 11 18 20
12 2 8
5 10 43 38 180 230 600 113
1 2 3 4 5 11 18 16 20
13 11 9
5 10 28 46 280 230 290 150 113
1 2 5,6 11 18 20
14 3 6
5 10 424,457 366 970 375
1 2 3 4 5 9,10 14 15 17 20
15 2 10
5 15 32 31 60 375,188 450 136 173 113
1 2 5 9,10 14 15 17 20
16 1 8
8 15 120 425,363 305 272 346 225
Table 3. A schedule description No. operation Product
type Operation description Start processing time
(min.) on the
machine
( 6,1) 1 Supply, weigh Analgin 0 1
(76,1) 14 Supply, weigh Paracetamol 5 1
(53,1) 9 Supply, weigh Europirin T 10 1
… ... ... … …
(69,3) 13 Granulate Paracetamol Sinus 1923 3
(74,4) 14 Blister pack Gultig 1
Paracetamol 3434 11
( 8,1) 1 Granulate Analgin 1951 3
(44,6) 7 Print box 1 Biseptrim 3389 16
… ... ... … …
(54,8) 10 Collective pack Europirin 22590 20
(60,8) 11 Collective pack Eurosept 22925 20
The measure unit for the schedule makespan is regularly the eight-hour shift. Examples of some other two objectives are: minimizing the number of late operations compared to 44 shifts value and minimizing the average ratio of idle times in the workshop.
Optimization Models for (MOF)JSSP
Scheduling in manufacturing has an applicative importance first of all for the production management department, because of its role in objectives accomplishment at production level (profitability, a high market share, product excellence etc.). The scheduling constitutes an active research subject also for the operational research area, for the combinatorial optimization, for cybernetics and even for the system control theory.
In the flexible job shop scheduling systems, the asynchronous events dynamics, the parallel evolutions in time of the events, the competition for the resources and the conditional dependences are not only present, but determinant (Panaitescu, 2006). The most adequate model to describe these systems is the discrete-event system model (DES).
A mathematical model which accepts all the tangible and intangible factors that determines the evolution in time of a DES is overly complex (hundreds or even thousands of variables) to allow analytical solutions. Therefore, for the representation, modeling and simulation of DES one must use tools of other type. These are conventional models and unconventional models.
Among the conventional models there are to be mentioned:
o waiting systems;
o Petri nets;
o general decision models;
o logical formulations such as STRIPS language;
o Markov processes;
o Monte Carlo simulation.
The unconventional models are procedural models and include, among others:
o agent-based models;
o genetic algorithms;
o expert systems and knowledge-based systems;
o fuzzy techniques;
o neural networks.
Waiting Systems
A job shop scheduling system can be modeled as a waiting system, where a number of clients (jobs) may be waiting some services from the manufacturing line (Panaitescu, 2006).
Performing a service consists, in the JSSP context, in completing a sequence of operations on the machines in the job shop. After the sequential run over the entire set of required operations, a client is totally served and can leave the process, as figure 2 depicts (example for a waiting thread formed by only three jobs in the drugs industry instance). When flexible JSS is the case, different clients can require different successions of operations, and is allowed some operations to be executed on one of many available resources.
Serving control in a waiting system involves accuracy in operations sequences order for all clients, accuracy in resource allocation and unloading for every operation, performing some type of service as soon as a resource becomes available for that operation (this will lead to a maximum number of served clients, in different stages) and reproducibility of performing services without circular blockages by reason of shared usage on some resources (Păstrăvanu et al., 2002).
This approach, based on client-server relationships, is adequate when the main purpose is not to optimize a function, but to balance waiting costs with serving costs. Additionally, the model is
mainly oriented on random client arrivals, on serving on few identical posts and it does not consider the flexibility aspect of scheduling.
Fig. 2. A JSS process model as waiting system (Nicoară, 2011, adaptation on (Paraschiv and Rădulescu, 2007))
STRIPS Language
STRIPS (Stanford Research Institute Problem Solver) is a descriptive language proposed by Fikes and Nilsson (1971) for knowledge representation domain. It is adequate for both job representation and job scheduling. STRIPS logical formalization is based on states (represented as sets of logical statements) and actions (with preconditions and effects).
For the FJSSP, STRIPS representations involve relations such as antecede(i, j1, j2) to formalize that in job i, operation j1 is antecedent to operation j2 and actions such as schedule(i1, j1, i2, j2) to schedule operation oi2,j2 after operation oi1,j1.
The extensions of the base language contain also negation, conditional effects, state variables, quantifiers and concurrent actions.
STRIPS model allows divide et impera strategies (which prove to be efficient to job scheduling) and this is the major advantage of the model. Various studies on jobs representations and scheduling algorithms, such as (Gelfond and Lifschitz, 1993), show instead that other representation languages are more suitable than STRIPS to simulate and solve the real scheduling problems. Such languages are the genetic-based representation languages.
In part II of the research the other optimization models for (MOF)JSSP will be described and analyzed.
Conclusion
The complexity of scheduling in manufacturing when the context is not simple - namely when the jobs to be scheduled are structurally different (regarding number of operations and processing order on the machines), when there are flexible routings on the machines for the jobs and multiple objectives are required - led to different approaches in optimization modeling for this kind of processes. All these approaches follow the general discrete-event system model; in fact, they are particular timed DES. As the evolution in time of flexible scheduling is also complex, analytical formulations for (MO)FJSS models are not available. Among the various descriptive and prescriptive optimization models, the waiting systems is especially suitable to stochastic scheduling and is quite limited regarding the flexibility characteristic. The STRIPS model allows a rigorous formalization for states and events in the system, but the proper strategies based on this language to optimally schedule becomes too complex for the big real
Clients arrival
waiting thread
Clients departure Performing service for clients
(processing jobs on the machines)
scheduling problems. In part II of the research other optimization models, more adequate to MOFJSSP, are to be analyzed.
References
1. A p p l e g a t e , D . , C o o k , W . , A computational study of the job-shop scheduling problem, ORSA Journal on Computing 3, 1991, pp. 149-156.
2. B r u c k e r , P . , S c h l i e , R., Job-shop scheduling with multi-purpose machines, Computing 45(4), 1990, pp. 369-375.
3. F i k e s , R . E . , N i l s s o n , N . J . , STRIPS: A new approach to the application of theorem proving to problem solving, Artificial Intelligence 1, 1971, pp. 27-120.
4. J a i n , A . S . , M e e r a n , S., A State-of-the-Art Review of Job-Shop Scheduling Techniques, European Journal of Operations Research 113, 1999, pp. 390-434.
5. G e l f o n d , M . , L i f s c h i t z , V . , Representing action and change by logic programs, Journal of Logic Programming 17, 1993, pp. 301-322.
6. N i c o a ră, E.S., Contribuţii privind utilizarea algoritmilor genetici la conducerea ordonanţării flexibile multiobiectiv a producţiei multisortimentale, doctoral thesis, Petroleum-Gas University in Ploieşti, 2011, pp. 105-109, 115-127.
7. N i c o a ră, E . S . , F i l i p , F . G . , P a r a s c h i v , N., Simulation-based Optimization Using Genetic Algorithms for Multi-objective Flexible JSSP, Studies in Informatics and Control, vol. 20, Issue 4/2011, ISSN 1220-1766, pp. 333-344.
8. P a n a i t e s c u , G . M . , Modelarea şi simularea sistemelor de producţie, note de curs, Universitatea “Petrol-Gaze” Ploieşti, 2006.
9. P a r a s c h i v , N . , Răd u l e s c u , G., Introducere în ştiinţa sistemelor şi a calculatoarelor, Matrix Rom Publishing House, Bucureşti, 2007.
10. Păs t răv a n u , O . , M a t c o v s c h i , M . , M a h u l e a , C . , Aplicaţii ale reţelelor Petri în studierea sistemelor cu evenimente discrete, Gh. Asachi Publishing House, Iaşi, 2002.
Modele de optimizare pentru ordonanţarea flexibilă multiobiectiv a producţiei multisortimentale (I)
Rezumat
În domeniul producţiei, cele mai dificile probleme în legătură cu obiectivul de eficienţă temporală apar frecvent când sarcinile de planificat sunt eterogene, când există posibilitatea rutelor alternative pe maşini ale sarcinilor şi când se impun obiective multiple. Acest cadru, numit Probleme de Ordonanţare Flexibilă Multiobiectiv a Producţiei Multisortimentale (POFMOPM), a fost formalizat, modelat şi studiat în ultimele decenii din multiple perspective pentru a surprinde toţi factorii de influenţă principali şi pentru a rezolva optim problema multiobiectiv astfel încât toate restricţiile specifice să fie satisfăcute.
Autoarea a orientat cercetarea asupra diverselor modele de optimizare adecvate proceselor PO(FMO)PM, atât convenţionale cât şi neconvenţionale: reţelele Petri, sistemele cu aşteptare, modelele decizionale generale, formulările logice de tipul limbajului STRIPS, procesele Markov, simularea Monte Carlo şi modelele procedurale (modelele bazate pe agenţi, algoritmii evoluţionişti, sistemele expert, tehnicile fuzzy, reţelele neuronale). Structura, clasificarea şi analiza modelelor de optimizare este în mare parte nouă, deoarece în literatura de specialitate modele pentru procesele POFMOPM sunt mult mai puţin raportate decât în cazul proceselor de ordonanţare a producţiei multisortimentale (POPM).
Toate modelele sunt analizate în studiul realizat (care este divizat în două părţi) în cazul general şi pentru un proces POPM particular din industria de medicamente bazat pe peste 600 de operaţii de planificat. Concluziile primei părţi se referă la complexitatea POFMOPM în producţie şi la rezultatele analizei a două modele de optimizare: sistemele cu aşteptare şi limbajul STRIPS. Rezultatele întregii analize (partea I şi II) indică limitele şi aspectele critice ale tuturor modelelor menţionate anterior şi caracteristicile proceselor care reclamă drept cele mai adecvate anumite modele de optimizare.
