Programming and scheduling techniques pdf

Additionally, we show the computational benefits of using our heuristic ModReg. The goal of this work is to address the aforementioned challenges and bring optimization-based scheduling techniques closer to industrial applications.

Computers Posted on Skip to content. Programming and Scheduling Techniques. Author : Thomas E. Answers to Exercises in Programming and Scheduling Techniques. As the case bases grow, the accuracy of the system should improve. A CBR model is presented by Schmidt for production scheduling problem. The model merges CBR with the theory of scheduling to solve production planning and control using an iterative problem-solving framework.

The study reported that the schedules attained by this approach are of acceptable level. A production scheduling system for parallel injection modeling machines in an electrical appliance company has been developed by Lin et al The architecture and data interface of the system is presented.

A Tabu-search with case-based reasoning model has been developed by Grolimund et al for incapacitated and capacitated facility location problems.

The model investigates the use of AI technique for configuring a basic meta-heuristic without any user interface. A case-based reasoning model has been developed by Dong et al for production scheduling system.

The objective of the model is to find a promising sequence for job processing. In this system, a schedule case is represented in the form of ordered tree and each job is represented in the format of attribute- value pairs. Li et al. Four sources of production disturbances have been identified; incorrect work, machine breakdowns, rework due to quality problem, and rush orders.

Martiez et al developed an automatic resource scheduling system ARSS , which is a computer based tool to keep, benchmark, and use customers and resources information to improve the quality of services while improving the productivity of the resources used in a service granting organization.

Hamada et al used interdigitation approach, expert systems, and GAs to develop an optimization technique solver for Steel-making scheduling problems. The approach is based on dividing a problem into several subproblems without losing its original structure and applying the most suitable solving method to each subproblem. A petri net is a graphical and mathematical modeling tool. It consists of places, transitions, and arcs that connect them. A model for scheduling piecewise constant product flows using a petri-net approach has been presented by Porth et al The model presents manufacturing systems as controllable output petri-nets.

The model can generate near optimal schedule of acceptable level. A new extended stochastic high-level evaluation petri-net model is suggested by Yan et al for scheduling and simulation of FMS. The structural and methodological features of a new optimal planning and dynamic scheduling system for a total plant continues petri-net manufacturing process is presented by Rong et al Hybrid petri-net, a combination of timed continuous petri-net and extended petri-net, is developed to model the process together with static equipment models and expert knowledge.

A heuristic search approach for scheduling FMS with due date based on petri-net state equation has been presented by Jeng et al In the model, the jobwise petri-net is introduced. N jobs are split into N jobwise nets and then are combined to formulate the state equations where the search algorithm can be implemented.

The objective of the model is to minimize weighted tardiness. The Study shows that the resulted solutions are very near to the optimal solution. With beam search only the most promising nodes at level K are selected as nodes to branch from.

The remaining nodes at that level are discarded permanently. The number of nodes retained is the beam width of the search.

Lotfi Zadeh pioneered it in approximately Fuzzy sets are actually functions that map a value which might be a member of the set to a number between zero and one indicating its actual degree of membership. A beam search heuristic approach has beem presented by Sabuncuoglu et al In this model, at any level only the promising nodes are kept for further branching and remaining nodes are prund off. The presented model is used to schedule job shop problem. Both the makespan and mean tardiness are used as the performance measures.

The proposed model is compared with other search methods and heuristic search. The study shows that the developed beam search is very competitive and promising tool.

A beam search model has been introduced by Sabuncuoglu et al for reactive scheduling in job shop environment. The study tests scheduling policies under machine breakdowns in a classical job shop system. Also, the effect of system size and type of work allocation on system performance is measured. The performance of the suggested model is measured as a function of tardiness and makespan criteria. Beam search-based algorithm for scheduling flexible manufacturing system has been introduced by Ihsan et al The performance of the algorithm is compared with several machine and vehicle dispatching rules using mean flow time, mean tardiness, and makespan.

The study indicates better performance of the proposed algorithm over the most dispatching rules. A model of local search algorithms for flow shop scheduling with fuzzy due-dates is developed by Ishibuchi et al In this model the due date for each job is given as a fuzzy set. The membership function of the fuzzy due-date corresponds to the grade of satisfaction of a completion time.

The objective function is to maximize the minimum grade of satisfaction over given jobs. SA and Tabu-search are applied. The performance of the model is compared to computer simulation. Simulation shows that the algorithm does not work well for fuzzy flow shop scheduling problem. And a new approach is proposed by changing the objective function. A fuzzy petri-net algorithm is developed by Xu for scheduling of flexible manufacturing systems with the human operators.

The model used the fuzzy reasoning algorithm to achieve the optimum schedule for the FMS. A simple FMS, which deals with 2 job types associated with 2 processes each, 3 machines, and two types of operators are considered as an example of the study.

Further more, the most suitable dispatching rule depends on the selected performance criteria and the characteristics of the production system. Also, an extensive computer simulation is essential for the elaborated process of dispatching rules.

Although computer simulation approaches have the advantage of providing more natural approaches for interfacing with human expertise systems at modest computational cost, the results obtained are not even approximately optimal. Simulation takes long time to reach optimal solution due to its experimental nature. Also, heuristic rules used in simulation process ignore the possibility of global optimization Miller et al Although exact mathematical methods are more clever in achieving optimal solutions, the running times still go up exponentially in problem size.

While dynamic programming approaches can significantly reduce computational effort; the chief concern is with the large amount of space required to store the intermediate results calculated by this algorithm. The main advantage of branch and bound is that, after evaluating all nodes, the final solution is known with certainty to be optimal. The disadvantage of branch and bound is that it can be extremely time-consuming, since the number of nodes is often very large. This puts stringent demands on future intelligent computing tools for production engineering systems.

Besides the improvements listed above, the future intelligent systems should be characterized by: integration of AI methods in all production scheduling activities, development of hybrid system ANN and GA, SA and TS, In conclusion, intelligent computing systems in the future will most likely be integrated, modular and hybrid in nature.

The particular method utilized will be the method most appropriate for the particular module of the integrated system. Future systems will include all the techniques presented in this paper and further more. International Journal of Production Economics, 63 2 , BELZ, R. Decision Support Systems, 17 2 , CHAN, F. The set E defines precedence relation between tasks. A task cannot be executed unless all of its predecessors have completed their execution and all relevant data is available.

Task preemption and redundant executions are not allowed. Here, the minimum distance is calculated as the number of links along the shortest path between two nodes. It is obvious that distance matrix is symmetric with zero diagonal elements. The scheduling of DAG G onto A consists of determining the index of the associated processor and starting time instant for each of the tasks from the task graph in such a way as to minimize some objective function.

The usual objective function which we use in this paper as well is completion time of the scheduled task graph Tmax also referred to as makespan, response time or schedule length. The starting time of a task i depends on the completion times of its predecessors and the amount of time needed for transferring the data from the processors executing these predecessors to the processor that has to execute the task i.

This parameter is used to describe the characteristics of multiprocessor system. For shared—memory multiprocessors the communi- cation is faster since it consists of writing data from main electronic memory of one processor into global also fast memory and then into main memory of another processor. If the tasks are scheduled to the same processor, i.

Let us denote the set of immediate predecessors of task j by P red j , i. Equations 3 ensure that each task is assigned to exactly one processor. Inequali- ties 4 - 5 state that each processor can not be simultaneously used by more than one task. Inequalities 6 express precedence constraints together with communication time required for tasks assigned to different processors. Con- straints 7 define the sequence of the starting times for the set of tasks assigned to the same processor.

They express the fact that task j must start at least Li time units after the beginning of task i whenever j is executed after i on the same processor k. The last term of inequalities 7 , i.

The mathematical formulation of MSPCD given by 2 - 9 contains bilinear terms in the y variables, and therefore belongs to the class of mixed integer bilinear programs. In particular, 13 makes it possible to reduce the number of z variables by about half. The number of variables in the original model is O n6. Constraints 14 can be added to the formulation. The number of linearization constraints 10 - 12 is rather large: O n6. These lin- earization constraints were experimentally observed to slow down the solution process con- siderably, even when the y variables were relaxed to continuous.

Next, we show that a reformulation of the problem containing the reduction constraint system instead of the usual linearization constraints 10 - 12 is exact. The optimal solution cannot have a shorter execution time than the ideal load balancing case, i. Furthermore, the length of final schedule can not be smaller that the length of the critical path, the longest path connecting a node with no predecessors to a node without successors. Let us denote by Succ j the set of immediate successors of task j, i.

Notice that this lower bound is valid throughout the whole solution process and does not depend on the current Branch-and- Bound node being solved. For any given Branch-and-Bound region, some of the variables are fixed.

For MILPs which model a combinatorial problems, more efficient heuristics are usually available based on the graph structure of the problem. These heuristics are seldom applicable to a Branch-and-Bound algorithm because at any given Branch-and-Bound iteration, some of the variables are fixed — and it is usually difficult to force the graph-based heuristics to constrain the parts of the graph structure which correspond to the fixed variables.

At the first iteration, however, no variables are fixed, which makes it possible to apply the efficient graph-based heuristics as a kind of pre-processing step to the whole Branch-and-Bound run. We describe our test examples in the next subsection, while the comparative numerical results are presented in Subsection 5. In addition, we tested a few examples with known optimal solutions generated as in [5] which proved to be hard instances for meta-heuristic methods.

We selected examples with different characteristics in order to examine the influence of task graph parameters on the efficiency of model-based solution methods. The value for fp is calculated based on the number of processors, number of levels within task graph and the average number of tasks per level. This definition is different from the one given in [11] and it is more realistic since it depend on various parameters.

For example, the counter is task graph containing 5 tasks that was used in [3] to illustrate the need of combining different heuristics during the scheduling process. Its CP based schedule onto 2-processor system happen to have longer execution time then the sequential one. Test is multistage graph with a good balance between parallelism and dependencies between tasks.