One of the basic and significant problems, that a shop or a factory manager is encountered, is a suitable scheduling and sequencing of jobs on machines. One type of scheduling problem is job shop scheduling. There are different machines in a shop of which a job may require some or all these machines in some specific sequence. For solving this problem, the objective may be to minimize the makespan. After optimizing the makespan, the jobs sequencing must be carried out for each machine. The above problem can be solved by a number of different methods such as branch and bound, cutting plane, heuristic methods, etc. In recent years, researches have used genetic algorithms, simulated annealing, and machine learning methods for solving such problems. In this paper, a simulation model is presented to work out job shop scheduling problems with the objective of minimizing makespan. The model has been coded by Visual SLAM which is a special simulation language. The structure of this language is based on the network modeling. After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented and compared with other results reported in the literature. Finally, the model output is analyzed.
Scheduling is allocation of the resources for performing a set of jobs at a certain time. Some instances of scheduling are course/exam timetabling at institution or school, examining the patients at clinics, scheduling for using facilities in a computer center, scheduling for maintaining and repairing production machines, and sequencing the jobs that arrive at one or more work center (Baker, 1974). One type of scheduling problem is job shop scheduling, objective of which may be minimizing the makespan or minimizing the tardiness penalty (Sule, 1997). This paper deals with the job shop scheduling problem with the objective of minimizing the makespan.
Linear programming and branch and bound methods are optimizing methods for solving this kind of problems, but they are utilized for small problems (Pinedo, 2001). Shifting bottleneck heuristic method is one of the successful heuristic methods for minimizing makespan in a job shop problem. In this procedure each unscheduled machine is considered as a separate single machine, and the machine that gives the maximum delay in a single job is identified as a bottleneck machine being scheduled first. In the modified version of the method named MODSB (Modified Shifting Bottleneck Heuristic), each unscheduled machines is considered as a separate single-machine problem. Then, the machine with the largest minimum tardiness is picked up as the bottleneck machine and is sequenced first. Another approach is a two-stage job shop scheduling heuristic method in which in the first stage an initial feasible near-optimal sequence is developed and at the second stage the near optimal solution is worked out ( Sule, 1997).
Bianco, Dellolmo, Giordani, and Speranza (1999) have minimized the makespan in a multimode multiprocessor shop scheduling problem. Each task can be undertaken by any methods in a set of pre-defined alternative modes, where each mode specifies a required set of assigned processors and a processing time. At any point of time, each processor can be used at most by only a single task. A general precedence constraint exists among tasks, and task preemption is not allowed. The problem consists of assigning to each task of each processor, a mode, a starting time, and precedence constrains to minimize the time required to complete all tasks. There are two constructive heuristic algorithms to compute a feasible solution of the problem. The first one is a deterministic algorithm that iteratively assigns execution modes and starting times to unscheduled tasks simultaneously on the basis of a partial schedule. The second one is a stochastic algorithm that schedules tasks in a given mode with probabilities proportional to task priorities. To work out the problem three lower bounds have been suggested.
Akpan (1996) has introduced a network technique that is a very useful tool for analysis of job shop sequencing problems. This technique offers a basis for finding an optimum solution. He has indicated that it is not correct to regard the network technique only as a project management tool, since it has a wider range of potential applications in other fields of engineering management. In this technique, the jobs priority on machines is determined by FCFS (First Come, First Serve) rule. Guinet (2000) has proposed a procedure for solving job shop scheduling problems. In this procedure, the objective is to minimize the maximum completion time of jobs. Here, firstly instance, the job shop problem is reduced to a flow shop problem by introducing job precedence constraints. Then, Johnson's rule is applied to solve the problem. Lee, Piramuthu, and Tsai (1997) have proposed to combine capabilities of genetic algorithms and machine learning techniques in order to develop a job shop scheduling system.
Blazewicz, Domschke, and Pesch (1996) have presented an overview of solution techniques for solving job shop problems. After a brief round up of all the trends and techniques, they concentrated on branching strategies and approximation algorithms belonging to a class of opportunistic and local search scheduling. They also deducted that local search methods are the most powerful tools to schedule job shops. Lorenco (1995) has presented a computational study of different local search and large-step optimization methods to solve the job shop scheduling problem. She has proposed a two-phase optimization method, known as large-step optimization, which has been recently introduced for the traveling salesman problem. Computation results show that large-step optimization methods outperform the simulated annealing method and find more frequently an optimal schedule than other methods. Sabuncuoglu and Bayiz (2000) have studied reactive scheduling problems in a stochastic manufacturing environment. An active schedule has the property that no operation can be started earlier without delaying another job. Specifically they have tested several scheduling policies under machine breakdowns in a classical job shop system. In their researches, the performance of the system is measured for the mean tardiness and makespan criteria.
Yu and Liang (2001) have presented a hybrid approach combining neural networks and genetic algorithms to solve the expanded job shop scheduling problem. This problem is a practical production scheduling problem with more restrictive processing constraints. Its objective being more general than those of the standard job shop scheduling problem. In this case, the genetic algorithm is used for the optimization of the sequence and a neural network produce is used for optimization of the operation start times with a fixed sequence. Blazewicz, Pesch, and Sterna (2000) have proposed a new time and memory efficient representation of the disjunctive graph. It has a form of a graph matrix that combines advantages of a few classical graph representations enabling easy operation on the problem data. Rahmati (1998) has proposed a hybrid genetic algorithm for non-classical job shop scheduling problems.
The papers acknowledged in this paper were close to our research areas, but used different objective functions. In addition, these papers have considered small-sized problems. A few papers have used simulation methods for solving different problems as well as flow shop scheduling. Emre (2001) has employed response-surface mapping methodology via regression analysis for reliable and static due date setting in multi-job shops. He has used the results obtained by computer simulation for the validation of setting due date. Satake, Morikawa, Takahashi, and Nakamura (1999) have proposed a simulated annealing method based on the rescheduling activity of the human scheduler in order to void local search solution for solving job shop scheduling.
Steinhöfel, Albrecht, and Wong (1999) have presented two simulated annealing methods for solving job shop scheduling. They have used a new neighborhood relation characterized by a large number of arcs. In this paper, we propose a computer simulation based on the network modeling using Visual SLAM to solve job shop scheduling. One of the main advantages of Visual SLAM is that its structure is based on the network modeling and it is very easy to add or remove attributes of the system. The second advantage is that it is a good tool for the manager of the system to obtain statistical reports in order to make good decisions for different experiments. The output of this model contains valuable information about machine utilization, idle time for each machine, the average queue length of jobs for each machine, and the average waiting time of jobs for each machine. This output also gives jobs sequence on each machine in job shop scheduling problems.
Five test problems for job shop scheduling problems have been conducted in this paper. Computational results show that the simulation procedure with Visual SLAM is an efficient tool for solving job shop problems with minimizing the makespan, especially for large-scale problems. The user has to rebuild the model based on the number of jobs and machines given in the problem. The result obtained from the simulation output helps managers to evaluate the performance of the system by knowing machines utilization and other resources, average waiting time of jobs, and average idle time for each machine. A new hybrid or any meta heuristic method can be proposed to solve very large-sized problems for further studies.
