شبیه سازی های جاسازی شده در یک سیستم برنامه ریزی کار چند پردازنده با بازرسی

This paper first develops architecture for a multiprocessor job scheduling system with an embedded simulation technique. The architecture provides a shell for applications that are characterized by two scheduling policies, a heuristic algorithm policy and a First-In-First-Out (FIFO) policy. These policies are implemented in the simulation model by using the embedded technique. The paper evaluates these two policies using the queue length, waiting time and flow time as the criteria to compare the performance of these two scheduling policies. Next we designed two simulation situations using two different real world applications. The purpose is to examine the performances of multiprocessor systems with and without inspection operations and two different scheduling policies. The two applications, berth allocation for the container terminal operations and production scheduling arrangement in an Original Equipment Manufacturer (OEM) power supply factory, are studied. The final results show that a proper scheduling policy will perform better than the traditional FIFO approach for a multiprocessor system. Our study also provides guidelines on balancing a system with the addition of a final inspection activity.

1.1. Multiprocessor job scheduling and its extensions with inspection operations Multiprocessor task scheduling (MTS) problem defines one type of task scheduling problems such that each task is processed by multiple processors (machines) simultaneously and no preemption is allowed (cf., Drozdowski, 1996 and Li et al., 1997). Applications of MTS include human resource planning, diagnosable microprocessor system, berth allocation and manufacturing systems (cf., Chen & Lee, 1999) among others. Recently, inspection activities become more important for certain type of MTS problems. U.S. government has taken several actions to against terrorist attacks. For instance, Container Security Initiative (CSI) program helps increase security for containerized cargo shipped to the United States (cf., Roach, 2003). CSI sets a goal that 85% of containers heading for U.S. need pre-screened before entering U.S. on CSI seaports in the world. Accordingly, container security inspection operations are important in these seaports. Another example of inspection activity comes from manufacturing systems. The quality inspection for final products becomes a standard production step for most manufacturing factories. Either security check or quality assurance will have serious impacts on the whole system when inspection rate does not match processor service rates. We consider this type of problems as multiprocessor task scheduling with inspection operations (MTSI). 1.2. Relevant literature Two common approaches can solve MTS problems, through optimization or approximation algorithms, or through simulation. Since many deterministic MTS problems were proven NP-complete (cf., Lee & Cai, 1999), it is difficult to find optimal solutions. Thus, previous studies on this area are focused on developing heuristic algorithms to find near-optimal solutions. For instance, Chen and Lee (1999) studied a one-job-on-multiple-machine problem. They developed a pseudo-polynomial time algorithm to solve optimally two machine problems, and provided a heuristic to solve three machine problems. Guan, Xiao, Cheung, and Li (2002) developed a heuristic algorithm to study the similar type of multiprocessor task scheduling problems with the application in berth allocation. This heuristic algorithm provides a relative error within 100% with both weighted and unweighted processing time cases. More recently, Caramia, Dell’Olmo, and Iovanella (2005) designed a heuristic to provide a lower bound for the objective of minimizing makespan in which non-consecutive multiprocessors are allowed to process one job. Ying and Lin (2006) developed an Ant Colony System heuristic to solve multiprocessor task scheduling problem in a multistage hybrid flow-shop environment. For the given number of jobs, job processing times, and the required quantity of machines at each stage, their approach performs better comparing with Genetic algorithm and Tabu search approaches. Huang, Chen, Chen, and Wang (2007) developed a simple linear time approximation scheme for MTS problems on four processors and the makespan is bounded by a constant number 1.5. Lagrangian relaxation and other decomposition based optimization approaches are also utilized to solve the multiprocessor task scheduling problems (cf., Guan and Cheung, 2004, Jansen and Porkolab, 2002 and Jansen and Porkolab, 2005). In all these previous works detailed analysis and mathematical insights were studied. Most of these algorithms provided a solution approach for deterministic processing time cases. In reality, deterministic processing time cases happen rarely and instead, most MTS problems contain uncertain processing time, which means the same size jobs may have slightly different processing times, or the same processor dealing with the same type of jobs may have different processing times. If uncertain processing times are considered in MTS problems, the efficiencies of all existing algorithms need to be reevaluated. Simulation is another approach for MTS problems with uncertain processing times and effective to find performances for stochastic systems. It also provides a friendly interface, visualizes results and easily deals with time-dependent events. However, unlike the optimization approach, simulation often uses experimental methods based on general principles or manipulated experiences. It is difficult to find an optimal or near-optimal solution by simulation itself. El Sheikh, Paul, Harding, Harding, and Balmer (1987) developed a simulation model for port operation, in which ships are assigned on berths based on yearly observation. Tahar and Hussian (2000) applied process-oriented simulation software “ARENA” to analyze the performance of container berth system in Kelang harbor. The berth allocation rules were fixed in four polices in the simulation model. Alattar, Karkare, and Rajhans (2006) used simulation tools to analyze container terminal development policies. In their simulation model, cost is the main factor to decide the location of cranes or berths. Effective processor allocation is an issue for many practical MTS problems. However, complicated processor allocation regulations make it difficult to implement the system by process-flow type simulation modeling. In this paper, we employ embedded simulation technique to model MTS problems by process-flow type simulation and take advantages of both optimization and simulation approaches. An embedded simulation is a technique that simulation is used as a part of a decision support system (cf., Banks, 1998). Embedded simulations can be used to estimate certain parameters, and those parameters can be used as the input for another model. For instance, Wu and Wysk (1989) used an embedded simulation to explore the concept of simulation-based floor shop control. Seifert, Kay, and Wilson (1998) used hierarchical simulation, an alias of embedded simulation, to evaluate AGV routing strategies. Soundarapandyan (2004) used embedded simulation to study order promising. The author developed a task generator for an ongoing make-to-order production system. Another application of embedded simulation is to combine different types of models together. Lee, Cho, and Kim (2002) used embedded technique to combine discrete and continuous modeling approaches for supply chain management applications because the nature of supply chain is neither completely discrete nor continuous. In general, embedded simulation technique provides a flexible way for a modeler to combine other methodologies into the simulation model. 1.3. Our approach In this study, we build an algorithm embedded simulation model, i.e. two-level simulation, for MTS and MTSI with stochastic processing times. In the first level, we model physical layout of MTS and MTSI system with functions or blocks provided by simulation software. In the second level, a heuristic algorithm or FIFO is embedded to determine processor allocation. When running the simulation, processor allocation results from the second level embedded model will serve as inputs for the first level simulation model. That is, the second level simulation real-time updates the first level simulation status during the simulation run. Taking this advantage, a modeler can insert any optimization method by using embedded technique into a simulation model with great flexibility. Two applications will be studied in this paper. One comes from the berth allocation problem within container terminal operations. In this case, the berth is divided into several segments and these segments can be considered as processors. Due to different ship sizes, each ship may occupy several segments (processors). After berth allocation, a security inspection activity will be required to scan containers and find a suitable service rate for that inspection station activity. In this case, the berth allocation can be formulated as an MTS problem and the whole system can be treated as an MTSI problem. The other application comes from Original Equipment Manufacture (OEM) power supply industry. One assembly line usually works for one order at one time. However, in a busy season, it is a common event that the same order may be made by more than one production-unit. Several assembly lines will serve for the same order. Before shipping the final products to customers, products have to be checked in order to fulfill quality standard. In this case, the assembly operations can be treated as an MTS problem and the whole system can be treated as an MTSI problem. 1.4. Contributions and the organization of the paper MTS is widely studied by optimization approaches but without considering uncertainties in real cases. Besides, MTS is hard to implement by simulation, uncertainties can only be considered in some simple cases, which rarely happed in the real world. Although the embedded technique provides a way for combining simulation and optimization approaches, it is still hard to embed MTS algorithms into the simulation model, due to the fact that each task is processed by multiple processors simultaneously. In this paper, our contribution lies in the following aspects: (1) In this paper we deal with the multiple processors scheduling problem under the scenario that each job will be processed by several consecutive processors simultaneously, such as the berth allocation problem or the OEM factory system as described. It is very difficult for commercial simulation software with default functions to deal with this type of problems, especially for the problem we deal with in this paper. In the problem we study in this paper, the number of processors simultaneously occupied by each job highly depends on the input job size. Therefore, we develop a copy entity strategy as a facilitating tool to provide a programmer flexibility to manipulate a job that seizes several processors simultaneously. In this way we can implement MTS algorithm into a simulation model frame and take advantage of both the optimization and the simulation approaches for analyzing MTS and MTSI with both deterministic and stochastic processing time cases. (2) With more demanding for container security inspections in a container terminal or quality assurance in the factory, we extend the model for MTS to MTSI to find a strategy for an inspection center. It is common that an inspection activity is required in the system. It may become bottleneck in the system. Our simulation approach will determine a feasible service rate and how many inspection centers might be required to avoid a bottleneck due to the inspection activity. The remaining part of this paper is organized as follows. Section 2 describes model design and two scheduling policies: a heuristic approach and a commonly used FIFO scheduling policy. Detailed description of the simulation model is provided in Section 3. Section 4 demonstrates the verification of combining simulation and optimization algorithms through embedded technique. In Section 5, we describe two application problems: berth allocation and OEM factory cases. Based on the analytical results, discussions are given in Section 6, and finally in the last section, we summarize our study.

In this paper, we studied embedded simulation techniques combining heuristic and FIFO algorithms for the MTS and MTSI problems. It is difficult to implement embedded simulations or processing algorithms into most commercial simulation software even though certain object oriented simulation software provides an interface to connect user-defined functions. AweSim is one type of process flow simulation software that provides “Event” node in which we developed optimization functions written in C++. These functions are finally combined with the simulation approaches to implement MTS and MTSI systems. Because of the nature of MTS and MTSI that one job will occupy several consecutive processors simultaneously and where preemption is not allowed, we developed the copy entity technique in the embedded system to facilitate the simulation. Based on this technique, we implemented both the heuristic and FIFO policies for MTS problems. Simulation results indicate that heuristic algorithm performs better than FIFO policy for both berth allocation and OEM factory cases. Many MTS algorithm are developed for the deterministic processing time cases. However, deterministic processing time cases rarely happen in the real world. By combining optimization and simulation approaches together, this gives us the ability to extend deterministic algorithm functions to deal with stochastic processing cases. Due to the security and quality check in the terminal operations and factory activities, in this study, we extend MTS to MTSI model. We evaluate the service rate of the inspection center so as to run the whole system smoothly. The simulation results show that the service rate of the security inspection center should be around 9 times the processor service rate for the berth allocation case, and service rate of the quality inspection center should be about 10 times of the processor service rate. In practice, it is usually hard to achieve such high service rates. The solution is to increase the inspection rates or provide more inspection centers. In a real world problem this simulation technique could be used to balance the system by adjusting certain parameters that include sampling rate at inspection stations. In general, this study has provided a way to link optimization and simulation approaches to simulate berth allocation and OEM factory cases. In the future research, we will perform mathematical modeling analysis for the MTS and MTSI problems that include the case that each processor has different work capacities. We will also consider a cost analysis of the whole process and explore ways to optimally allocate resources.