Dynamic Scheduling In Manufacturing Systems - Report Example

Name: Instructor: Course: Date: Dynamic Scheduling In Manufacturing Systems Rescheduling Within Real-Time Events The problem of scheduling concerns the search for optimal (or almost optimal) schedules that are subject to several constraints. There are different approaches, which have been createdto assist in solving the challenge of scheduling (Fahmy, Tarek Hassan, and Hesham12). Nevertheless, most of these ways are usually impractical in changing real-world settings due to many unexpected disturbances. In many real-world situations,scheduling occurs continuously. Rescheduling in real-time events has to address how and when to respond to these events. When to reschedule; severalpolicies have been suggested by Framinan, Rainer and Rubén, regarding when to reschedulehybrid, and periodicevents. Some proponents accorded the hybrid and periodic policies special consideration (19). In the periodic policy, the generation of schedules happens at regular intermissions, in gathering all the available details fromthe floor of the shop. In the dynamic scheduling policy, the problem is disintegratedinto a sequence of static issues, which can be addressed using algorithms of classical scheduling. The execution of the schedule occurs and is not reevaluated until the commencement of the following period, whereby the planning limit is renewed through considering the new information obtained fromthe existing status of the shop floor. The periodic policy generates less schedule nervousness and more schedule steadiness. Unfortunately, succeeding aconventional schedule in light of the important transformations in the status of the shopfloor may interferewith the performance because unwanted intermediates or products may be produced. Additionally, the determination of the rescheduling period is a hard task (Aydin and Öztemel 169). Bongaerts et, al. investigated the manner under which the occurrence of scheduling in a vibrant job shop environment influenced the outcome where the variations machine breakdowns and processing time may occur haphazardly (123). At every rescheduling time, static schedule for the existing jobs is produced by a transmitting rule. As expected, performance worsenswith an increase in the rescheduling period. Petrovic and Duenas applied the policy of the rolling horizon for one machine dynamic scheduling challenge with a set-up that is sequence-dependent (22). Their discovery was that the rolling horizon scheduling outdoesthe myopic rules of dispatching. Brennan and Norrie researched on the frequency of rescheduling within a flexible environment of a multi-processmanufacturing system for processing time variations and machine breakdowns (236). The measurement of the performance of the system occurs in order to determine the make span criteria and mean tardiness. Their outcome on the inquiry on the frequency of scheduling showed that a periodic reaction with a suitable period lengthwould be enough in handling real-time events. Their observation was that the machine breakdowns experienced moresignificant impacts on the outcome of the system than in processing time variations. In the event drivenpolicy, system rescheduling is initiatedin reaction to an unanticipated event, which alters the existing status of the system. Most of the methodologies towards dynamic scheduling employ this policy. According to Bongaerts et al., in an event motivated rescheduling policy for a job shop that has an unplanned breakdown in machines, rescheduling is initiated when a breakdown happens (127). These outcomes prove that that the event driven rescheduling containing a lower computational load and higher expectednessoutdoes the dispatching rules and the sequencing periodic policy. For a hybrid policy, events are normally considered upon the assumption of immediate jobs, machine breakdowns, job priority changes, and the cancellation of jobs. How to Reschedule; concerning thestrategies necessary for rescheduling, two methods can be used. According to Aydin and Öztemel, these methods are complete rescheduling and schedule repair (170). Schedule repair considerssome local alterationto the existing schedule, and this is usually preferred due to the latent saving in CPU periods the steadiness of the preservation of the system. Complete rescheduling renews a fresh schedule from the beginning, and this process may be better in sustaining optimal results, but these results are rarely attainable in practice, and they need excessive computation time. Additionally, complete rescheduling can lead to lack ofcontinuity and instability in complete plant schedules, generating into additional costs in production that are attributable to shop floor nervousness. Dynamic Scheduling Techniques According to Cavalieri, Garetti, Macchi, and Taisch, dynamic scheduling is solved through heuristics, metaheuristics, dispatching rules, multi-agent systems, and artificial intelligence techniques (139). Heuristics: In the context of dynamic scheduling techniques, Heuristics is a problem specific method of schedule repair and it does not assure to provide anoptimal schedule. Nevertheless, the technique has the capability of finding reasonably good answers within a short period (Liu, Serhan and Vidyadhar139). The most basic schedule reparation heuristics are partial schedule, right-shift repair schedule, and match-up repair schedule. The remaining operations schedules are shifted forwards by the right-shift heuristic operations schedule in good time by the level of downtime, in case of machine failure. The rescheduling of the strategy of match-up repair schedule occurs in order to conform withthe pre-schedule in the future. Repair reschedules of the partial schedule occurs only for the events in failure. Cowling and Johansson investigated the output of the right-shift heuristic in comparison to the complete rescheduling and dispatching rule using bound and branch (230). The results of their experiment exemplified thatright shifting outdoes complete rescheduling and priority rules. The right-shift heuristic for injecting idle time to describe predictable schedules was used by Cowling,Ouelhadj and Petrovic (459). Pamay, Kerem and Gündüz compared the output of partial schedule repair (influenced operations schedule repair), repair of right shift schedule and complete rescheduling with respect to efficiency measures (makespan) and deviation from the first schedule (219). Reschedules for the repair of the partial schedule heuristic entails only the operations that are affected by the disruption directly or indirectly in order to minimize both the rise in makespan, as well as the deviance from the first schedule. The outcomes demonstrated that the influenced heuristic operations minimize a lot of the computational complexity and deviation linked with complete right shifting and rescheduling. Several more definite heuristics schedule repairs have been suggested by Henning and Cerda (2315), for new job arrival, machine breakdown and process time variations. The other rescheduling methods areredirecting the jobs to substitute machines, complete rescheduling, and job splitting. Results from various experiments prove that heuristics portraysan excellent moderate performance with a diffident computational problem. Dispatching Rules: The dispatching rules have taken a major role in various contexts.There are several complex and simple dispatching rules, but these have been found not be as effective as would be expected. Therefore, there are many investigations that can be conducted in order to recognize the combination of some dispatching rules in order to find several system states, whereby the relative performance for each rule is maximum. In order to examine the output of various rules for dispatching, under variedstochastic and dynamic situations conditions of the floor of the shop, simulation can be used. The simulation process allows the effecting of different dispatching rules, whereby the rule, which yields the highest performance is considered. Krishnan, Chinnusamy and Karthikeyan used several simulations in order to examine the outcome of dispatching rules (2793). Herroelen and Leus offered outstanding reviews of dispatching rules in vibrant flow shops and job shops (289). They examined the output of several dispatching rules in line with some basic criteria for performance like maximum and minimum flow time, variance of tardiness, flow time variance, maximum tardiness, meantardiness, etc. These rules were categorized into five groups i.e. those rules comprising of process times, due dates, rules involving due neither dates nor process times, shop floor conditions rules, and rules associated with two or more than the initially named categories. Jahangirian and Conroy applied dispatching rules and simulation for scheduling a real-time flexible system of manufacturing the present entrances of machine breakdowns, tool breakage, and urgent jobs (247). Simulation examines the scheduler founded on this evaluation and the dispatching rules that satisfy the demanded criteria. Rajabinasab and Saeed applied simulation to analyze the performance of different schedule repair heuristics founded on redirecting of jobs to their substitute machines for unexpected failures in job shop machines (1091). Additionally, no rule executes well for all significant criteria associated with the tardiness of jobs and flow time. Meta-heuristics: This technique has been applied in solving production-scheduling challenges. Meta-heuristics involves genetic algorithms, simulated annealing, and tabu search. According to Pereira et al., meta-heuristics are top-level heuristics that direct local search heuristics to avoid local optima (190). The local searches are neighborhood search approaches that are founded on the notion of examiningneighborhoods. In these kinds of searches, the search commences from some provided solution, and attempts iteratively to advance to a better answer in asuitably defined neighborhood of the present solution through move operators. The process of searching process stops when no improvedresult can be found in the vicinityof the present answer that is the local optimum. Meta-heuristics like tabu search, simulated annealing, and genetic algorithms refine the local search algorithms to avoid the local optima either bytolerating worsesolutions, or through generating solutions that are good startingfor the local search using a more logical means than merely providing unplanned initial answers. Tabu search, simulated annealing, and genetic algorithmshave been greatly used to answer statically,deterministic challenges in the production of different domains as job shops, flow shops and open shops, batch processing, flexible manufacturing systems, etc. Nevertheless, little research workansweredthe application of meta-heuristics in vibrant scheduling. Boloori, Fatemi and Zandieh used simulated annealing in repairschedules for ground operations for the space shuttle (1964). In order to repair a schedule, the adopted system selects between five repairheuristics by using a selection-function, and relates the simulated annealing search to accomplishseveral repairiterations. The use of genetic algorithms by Xhafa shows the dynamic scheduling of processing job shops in the presence of alternate job routine and machine breakdown (77). Two measures of performancenamely average job cost and average job tardiness are used. Results by Xhafa and Ajith document that the outputs of genetic algorithms in providing schedules have more stability and are better makespans compared to the local search (608). Nevertheless, in their experimental outcomes, it is discovered that the capabilities of genetic algorithms normally diminish with a rising size of the problem and they are not efficient in finding an almost-optimalsolution in a sensible time. Artificial Intelligence Techniques: Many dynamic scheduling problems have applied artificial intelligence techniques like neutral networks, knowledge-based-systems, fuzzy logic, case-based reasoning, Petri nets, etc. The major driver of knowledge-based means is that there is anextensivediversity of technical resources on the corrective activities to be assumed in the presence of events in real-time. Knowledge-basedsystems pay attention to capturing the experience or expertise of an expert in a certain domain and a mechanism for inferenceis used to generate recommendations or conclusions concerning the corrective measure to undertake. Mönch et al. attempted to use a knowledge-based system in producing job shop scheduling (583). In this case, the author performed a constrainedstraightforward search to generate a schedule. The dynamic circumstances are controlled by rescheduling the impacted jobs by selectively calming some of the restraints. A knowledge-based system- OPIS was originally developed for processing production scheduling, and the technique uses an opportunistic problem solving approach incrementally to produce and revise schedules in reaction to changes. The schedule repairs defined by heuristics in OPIS areresource scheduler, the jobscheduler, left-shifter, demand swapper, and right-shifter. Another scheduling system of interactive knowledge-based scheduling based on interactive and opportunistic repair-based problem solving is IOSS. SONIA is a job-shop and knowledge-basedpredictive-response scheduling system. Several schedule repair heuristics that have been described include relaxing due dates, operation deferred until the proceeding shift, minimization of idle time and extending work shifts. Some researchers have provided simulations and collective knowledge-based systems for pursuing a better-off modelling capability of scheduling to choose on the best counteractive actions in order to accommodate the real-time activities Wong, Chwen-Tzeng and Chun-Hsien (2003). The development of some knowledge-based systems was meant to assist the users toreact interactivelyto real-time situations (Mönch et al. 583). Other techniques of artificial intelligence, which were used to address the challenge of dynamic scheduling, are case-based reasoning, petri nets, fuzzy logic, and neural networks. In order to generate better systems of dynamic scheduling, Barbati, Giuseppe and Andrea made hybrid systems which pooled several techniques of artificial intelligence (6020). These researchers developed the structure for schedule repairs in job shops using case-based logical reasoning. Cases signify the suitable repair actions and repair contexts. Case based reasoning gives room for capturing and re-using this knowledge in repairing similar circumstances. The schedule is incrementally repaired, when need arises using the cases kept within the system. Tao, Lin and Nee employed fuzzy logic and case-basedreasoning and fuzzy logic for active scheduling of the uninterrupted caster within the steel industry (4119). Additionally, Breese and Fehling applied fuzzy logic in diagnosing critical jobs eventually to reschedule them (1304). The consequence was that the decision-maker on the floor of the shop floor got the information regarding the jobs that have to be rescheduled. The system unites the flexible learning diagnostic procedures of knowledge-based and neural networks expert systems. Dynamic Scheduling of Multi-agent-based Techniques: Most of the control systems and scheduling created in industrial settings has been traditionally perceived as a top-down procedure and reaction, which heavily relieson hierarchical and centralized models (Tao, Lin, and Nee 4119). In order to guarantee there is constancy of data over the whole enterprise, hierarchical and centralized scheduling systems depend on central databases. To optimize the output, scheduling decisions should be made centrally at the supervisor’s level. Some proponentsprovide a central computer duty for scheduling, transmitting resources, dispatching corrective actions, and monitoring any deviation in this technique. Hierarchical and centralizedscheduling systems portray several drawbacks (Erol, Rizvan, et al. 1720). The main restraint is the presence of a central computer that comprises a bottleneck, which can limit the shop’s capacity, and it is the only point of failure, which can pull down the whole shop. Additionally, modifying the conformation of hierarchically directed manufacturing systems is time consuming and expensiveas it entails costly software rewriting. The systems of hierarchical scheduling in manufacturing are becoming progressively complex with the assimilation of manufacturing system constituents.Another demerit is that the up and down movement of information raises the latency period of decision-making. Further, practical experience has shown that hierarchical,centralized scheduling systems incline towards problems that reactto disturbances and are likely to fail in responding effectively to real-time presence. When a disturbance happens, it is injected back to the high hierarchy level, in which case the fresh schedule activates a new movement of commands, which forms the response to the disruption. This up and down flow of information causes a slow response time that leads to low vigor. In spite of the hierarchical and centralized scheduling systems capability in providing worldwide better schedules insettings where real-time turbulences are rare, it has been increasingly suggested that they are also found to be inadequate in responding toenvironments that are highly dynamic (Renna 1285). Thus, hierarchical and centralized scheduling isdifficult and complex in reconfiguring and maintaining, and they are slow in satisfying the requirements of current complex manufacturing settings. Some authors attest to the rising trend towards dispersed shop floor organizations. This happens because of the need for improving the responsiveness levels from the changes of the shop floor in technologies and markets. The main motivation in developing these systems is the need to decentralize the direction of the system of manufacturing, thereby minimizing the cost and complexity, improvingflexibility, and increasing fault easiness. Further, there is enough substantial proof that the multi-agent systems are among the promising approaches to developing robust, cost-effective, and complex manufacturing scheduling systems for the next generation because of theirautonomy, distribution, and dynamic form, and their strength against failures (Aissani, et al. 2513). The application of multi-agent systems in solving the challenge of dynamic scheduling is driven by the ability of the scheduling systems to recognize that control and data are dispersed through the plant. These systems comprise of autonomous agents committed to every functional or physical manufacturingbody in the facility like opinions, operators, parts, etc. Local autonomy permits the agents to assume responsibility for conducting local scheduling for a single or more entities within the process of production and to react efficiently and locally to local differences. This raises the flexibility and robustnessof the system. Additionally, these individual agents contain considerable latitude in addressing the local situations and cooperating and interacting with one another in order to attain global robust and optimal schedules. Evaluation of Solution Techniques This paper has identified several techniques of dynamic scheduling including simulation and dispatching rules, fuzzy logic, heuristics, neutral networks, meta-heuristics, hybrid techniques, and knowledge-based systems. In order to establish the value of the varied solution techniques, it is imperative that these techniques are compared. Al-Hinai and ElMekkawy provide that the dispatching rules are simple and can identify reasonable solutions hastily (280). Nevertheless, they offer a poor quality solution because of their myopic form. Heuristics has been greatly used to respond to the real-time events due to their simplicity, regardless of being stuck in deprived local optima in some situations. To go over this limitation, meta-heuristics like tabu search, genetic algorithms, and simulated annealing, have been suggested. A number of comparative researches have been given in order to compare the output of simulated annealing, tabu search, and genetic algorithms. Different from the tabu search and simulated annealing onoperating one feasible answer, geneticalgorithms manipulate and maintain a population of practical answers. It has been found that genetic algorithms are inadequate due to their inefficiency in finding a near-optimal answer in a logical time in comparison to the simulated annealing and tabu search, which work on one configuration as opposed to the whole population (Zhou et al. 32). It has also been discovered that the centralized scheduling systems give a consistent global perspective of the condition of the shop and universally better schedules. Nevertheless, practical experience has specified that these systems have a tendency of exhibiting problems such as the reactivity to conflicts. Localautonomy gives room to the agents to assume the duty of carrying out domestic scheduling for either of the physical or functional components in the process of production like jobs and machines. Agents are capable of observing their environmental setting and to linkor work with other agents in ways that ensure that the local schedules result to globally acceptable schedules. Yao et al. documented that autonomous architectures show prospects of minimized integrity, complexity, costs, and high robustness and flexibility against disturbances (125). Nevertheless, they experience problems in giving universally optimizedoutput and the impulsiveness of the system’s behavior in complex settings that contain a large figure of agents. Works Cited Aissani, N., Bekrar, A., Trentesaux, D., & Beldjilali, B "Dynamic scheduling for multi-site companies: A decisional approach based on reinforcement multi-agent learning." Journal of Intelligent Manufacturing 23.6 (2012): 2513-2529. Al-Hinai, Nasr, and ElMekkawy Trevor "Robust and stable flexible job shop scheduling with random machine breakdown using a hybrid genetic algorithm."International Journal of Production Economics 132.2 (2011): 279-291. Aydin, M. E. and Öztemel, Egin., job-shop scheduling using reinforcement learning agents, Robotics and Autonomous Systems, 33 (2-3), 169-178 (2000). Barbati, Maria, Giuseppe Bruno, and Andrea Genovese. "Applications of agent-based models for optimization problems: A literature review." Expert Systems with Applications 39.5 (2012): 6020-6028. BolooriArabani,.FatemiGhomi, and Zandieh Jaya "Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage." Expert systems with Applications 38.3 (2011): 1964-1979. Bongaerts, L., Monostori, L., McFarlane, D., and Kadar, B., Hierarchy in distributed shop floor control, Computers in Industry, 43 (2), 123-137 (2000). Brennan, R. W. and Norrie, D. H., Evaluating the performance of reactive control architectures for manufacturing production control, Computers in Industry, 46 (3), 235-245 (2001). Breese, John S., and Fehling Michael. "Decision-theoretic control of problem solving: Principles and architecture." arXiv preprint arXiv:1304.2343 (2013). Cavalieri, S., Garetti, M., Macchi, M., and Taisch, M., An experimental benchmarking of two multi-agent architectures for production scheduling and control, Computers in Industry, 43 (2), 139-152 (2000). Cowling, P. I. and Johansson, Michael, Using real-time information for effective dynamic scheduling, European Journal of Operational Research, 139 (2), 230-244 (2002). Cowling, P. I., Ouelhadj, D., and Petrovic, S., A Multi-agent architecture for dynamic scheduling of steel hot rolling, Journal of Intelligent Manufacturing, 14, 457-470 (2003a). Erol, R., Sahin, C., Baykasoglu, A., &Kaplanoglu, M "A multi-agent based approach to dynamic scheduling of machines and automated guided vehicles in manufacturing systems."Applied Soft Computing 12.6 (2012): 1720-1732. Fahmy, Amer, Tarek M. Hassan, and HeshamBassioni. "What is Dynamic Scheduling?." (2014). Print. Framinan, Jose M., Rainer Leisten, and Rubén Ruiz García."The Context of Manufacturing Scheduling."Manufacturing Scheduling Systems.Springer London, 2014.19-41. Herroelen, William. andLeus, Remy., Project scheduling under uncertainty: Survey and research potentials, European Journal of Operational Research, 165 (2), 289-306 (2005). Henning, G. P. and Cerda, J., Knowledge-based predictive and reactive scheduling in industrial environments, Computers and Chemical Engineering, 24(9), 2315-2338 (2000). Jahangirian, M. and Conroy, G. V., Intelligent dynamic scheduling system: the application of genetic algorithms, Integrated Manufacturing Systems, 11 (4), 247-257 (2000). Krishnan, M., T. R. Chinnusamy, and Karthikeyan, T. "Performance Study of Flexible Manufacturing System Scheduling Using Dispatching Rules in Dynamic Environment."Procedia Engineering 38 (2012): 2793-2798. Liu, Nan, SerhanZiya, and Vidyadhar Kulkarni."Dynamic scheduling of outpatient appointments under patient no-shows and cancellations."Manufacturing & Service Operations Management 12.2 (2010): 347-364. Mönch, L., Fowler, J. W., Dauzère-Pérès, S., Mason, S. J., & Olivia Rose "A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations." Journal of Scheduling 14.6 (2011): 583-599. Pamay, M. Berke, KeremBülbül, and GündüzUlusoy. "Dynamic resource constrained multi-project scheduling problem with weighted earliness/tardiness costs." Essays in Production, Project Planning and Scheduling. Springer US, 2014.219-247. Pereira, Ivo, Ana Madureira, P. B. de Moura Oliveira, and Ajith Abraham, "Tuning Meta-heuristics Using Multi-agent Learning in a Scheduling System." Transactions on Computational Science XXI.Springer Berlin Heidelberg, 2013.190-210. Petrovic, D., and Duenas, A., (2006), A Fuzzy Logic Based Production Scheduling/Rescheduling in the Presence of Uncertain Disruptions, to appear in Fuzzy Sets and Systems. Rajabinasab, Amir, and Saeed Mansour. "Dynamic flexible job shop scheduling with alternative process plans: an agent-based approach." The International Journal of Advanced Manufacturing Technology 54.9-12 (2011): 1091-1107. Renna, Paolo. "Multi-agent based scheduling in manufacturing cells in a dynamic environment." International Journal of Production Research 49.5 (2011): 1285-1301. Tao, Fei, Lin Zhang, and A. Y. C. Nee."A review of the application of grid technology in manufacturing."International Journal of Production Research 49.13 (2011): 4119-4155. Wong, Jui-Tsung, Chwen-Tzeng Su, and Chun-Hsien Wang."Stochastic dynamic lot-sizing problem using bi-level programming base on artificial intelligence techniques."Applied Mathematical Modelling 36.5 (2012): 2003-2016. Xhafa, Fatos, Joanna Kolodziej, Bernat Duran, Marcin Bogdanski, and Leonard Barolli."A Comparison Study on the Performance of Population-based Meta-Heuristics for Independent Batch Scheduling in Grid Systems." Complex, Intelligent and Software Intensive Systems (CISIS), 2011 International Conference on.IEEE, 2011. Xhafa, Fatos, and Ajith Abraham."Computational models and heuristic methods for Grid scheduling problems."Future generation computer systems 26.4 (2010): 608-621. Yao, S., Jiang, Z., Li, N., Zhang, H., &Geng, N. "A multi-objective dynamic scheduling approach using multiple attribute decision making in semiconductor manufacturing." International Journal of Production Economics 130.1 (2011): 125-133. Zhou, A., Qu, B. Y., Li, H., Zhao, S. Z., Suganthan, P. N., & Zhang, Q. "Multiobjective evolutionary algorithms: A survey of the state of the art." Swarm and Evolutionary Computation 1.1 (2011): 32-49. Read More