共查询到20条相似文献,搜索用时 578 毫秒
1.
This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance. 相似文献
2.
《European Journal of Operational Research》1996,94(2):292-301
We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well. 相似文献
3.
《European Journal of Operational Research》2001,128(1):129-146
The problem of scheduling jobs with distinct ready times and due dates in a single machine to minimise the total earliness and tardiness penalties is considered. A constructive heuristic, which determines the sequence of jobs and simultaneously inserts idle times, is proposed. Adjacent pairwise interchange is then applied to the schedule obtained. For problems involving at most 12 jobs the heuristic solutions are compared to optimal solutions. For larger problems with up to 80 jobs the heuristic is tested against a local search based on pairwise interchanges and four dispatching rules presented in the literature. In each case, idle times are optimally inserted. 相似文献
4.
Dispatching rules are simple scheduling heuristics that are widely applied in industrial practice. Their popularity can be attributed to their ability to flexibly react to shop floor disruptions that are prevalent in many real-world manufacturing environments. However, it is a challenging and time-consuming task to design local, decentralised dispatching rules that result in a good global performance of a complex shop.An evolutionary algorithm is developed to generate job shop problem instances for which an examined dispatching rule fails to achieve a good solution due to a single suboptimal decision. These instances can be easily analysed to reveal limitations of that rule which helps with the design of better rules. The method is applied to a job shop problem from the literature, resulting in new best dispatching rules for the mean flow time measure. 相似文献
5.
We investigate a new scheduling problem, multiple-orders-per-job (MOJ), in the context of a two-machine flowshop. Lower bounds for the makespan performance measure are provided for combinations of lot-processing and item-processing machines. An optimization model is presented that addresses both job formation and job sequencing. We define a heuristic to minimize the makespan for the MOJ problem for two-machine item-processing flowshops. The heuristic obtains solutions within 2% of a tight lower bound and runs in O(HF) time, where H is the number of orders and F is the restricted number of jobs. 相似文献
6.
The problem of scheduling orders at each facility of a large integrated steel mill is considered. Orders are received randomly, and delivery dates are established immediately. Each order is filled by converting raw materials into a finished saleable steel product by a fixed sequence of processes. The application of a deterministic mixed integer linear programming model to the order scheduling problem is given. One important criterion permitted by the model is to process the orders in a sequence which minimizes the total tardiness from promised delivery for all orders; alternative criteria are also possible. Most practical constraints which arise in steelmaking can be considered within the formulation. In particular, sequencing and resource availability constraints are handled easily. The order scheduling model given here contains many variables and constraints, resulting in computational difficulties. A decomposition algorithm is devised for solving the model. The algorithm is a special case of Benders partitioning. Computational experience is reported for a large-scale problem involving scheduling 102 orders through ten facilities over a six-week period. The exact solution to the large-scale problem is compared with schedules determined by several heuristic dispatching rules. The dispatching rules took into consideration such things as due date, processing time, and tardiness penalties. None of the dispatching rules found the optimal solution. 相似文献
7.
Lars Mönch Rene Schabacker Detlef Pabst John W. Fowler 《European Journal of Operational Research》2007
In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures. 相似文献
8.
9.
《European Journal of Operational Research》1997,103(1):129-138
The problem of scheduling in a flowshop is considered with the objective of minimizing the total weighted flowtime of jobs. A heuristic algorithm is developed by the introduction of lower bounds on the completion times of jobs and the development of heuristic preference relations for the scheduling problem under study. An improvement scheme is incorporated in the heuristic to enhance the quality of its solution. The proposed heuristic, with and without the improvement scheme, and the existing heuristics are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that both versions of the proposed heuristic perform better than the existing heuristics in giving a superior solution quality and that the proposed heuristic without the improvement scheme yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the proposed heuristic and the existing heuristics, as well as the effectiveness of a variant of the scheme. The results are also discussed. 相似文献
10.
The problem considered in this study is that of non-pre-emptive scheduling of the activities in a project network to minimize project duration under limited resource availabilities. Various heuristic rules and optimization techniques have been applied to this problem, and comparisons of their effectiveness have been made in the literature. However, no thorough investigation of the types of network and resource characteristics which play an underlying role in determining heuristic performance and which account for the variability of results has been made previously. In this study, a new heuristic rule which compares favourably with the widely-used heuristic rules is developed, and the influence of network/resource characteristics on the performance of different heuristic rules is investigated. 相似文献
11.
Jatinder N. D. Gupta 《Journal of Global Optimization》1996,9(3-4):239-253
This paper shows that the single machine scheduling problem with multiple operations per job separated by minimum specified time-lags is NP-hard in the strong sense. Seven simple and polynomially bounded heuristic algorithms are developed for its solution when each job requires only two operations. Empirical evaluation shows that the percentage deviation of the heuristic solutions from their lower bounds is quite low and the effectiveness of these heuristic algorithms in finding optimal schedules increases with an increase in the number of jobs. 相似文献
12.
This paper considers the problem of scheduling part families and jobs within each part family in a flowline manufacturing cell with independent family setup times where parts (jobs) in each family are processed together. The objective is to minimize total flow time. A branch-and-bound algorithm capable of solving moderate sized problems is developed. Several heuristic algorithms are proposed and empirically evaluated as to their effectiveness and efficiency in finding optimal permutation schedules. These results show that several heuristic algorithms generate solutions that are better than those generated by an existing genetic algorithm. 相似文献
13.
This paper analyses the total tardiness minimization in a flowshop with multiple processors at each stage. While there is considerable research to minimize the makespan, very little work is reported on minimizing the total tardiness for this problem. This research focuses on heuristic methods that consider this environment as a series of parallel machine problems. New dispatching rules are introduced. One of the proposed rules is able to deal with jobs that will come afterwards and not only the available jobs at the decision time. Dispatching rules are also associated with classical (forward and backward) and new list scheduling algorithms. A special scheduling algorithm able to deal with idle times is proposed. Computational experiments in a set of 4,320 literature instances show that the developed heuristics are competitive and outperforms their classical counterparts. 相似文献
14.
This paper addresses the two-machine flowshop problem where the setup, processing, and removal times of the jobs are separated and are independent of the job sequence. This problem is considered with maximum lateness as a measure of performance. Elimination criteria are established for both the classical and ordered flowshops, and optimal sequences are obtained for special ordered flowshops. 相似文献
15.
A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times
Hamidreza Eskandari Amirhamed Hosseinzadeh 《The Journal of the Operational Research Society》2014,65(8):1221-1231
This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods. 相似文献
16.
《European Journal of Operational Research》1986,24(3):424-438
We investigate the computational complexity of no-wait shops scheduling problems. The problem of finding optimal finish time schedules is shown to be NP-hard for flowshops with two machine centres where each machine centre has one or more parallel machines for processing tasks. The complexity results are also reported for no-wait shops scheduling when all nonzero tasks have unit or identical processing time requirement. A polynomial time algorithm for 3-machine flowshops is proposed for optimal finish time schedules. Finding optimal finish time schedules in 2-machine jobshops in NP-hard. Also we establish NP-hard results for 3-machine jobshops for both optimal finish time and mean flow time schedules. Some results are deduced with the present work and with those reported earlier. 相似文献
17.
LIXIN TANG 《运筹学学报》1998,(4)
1.IntroductionProductionschedulingcanbedefinedgenerallyastheallocationoftheresourcesinaproductionsystemovertimetoperformtheoperationsneededtotransformrawmaterialsilltoproducts.Aneffectiveandefficientschedulingsystemisnecessarytowellachievethepotentialsofaproductionfacility.Productionschedulingproblemsareextremelycomplex.Thecomplexityismainlyduetothefollowingtwofeaturesoftheproblem(Liu,1995).InterconnectedDecisions:Thecomponentsofaproductionsystem,e.g.,machines,ma-tenalhandlingdevicesandstora… 相似文献
18.
All large scale resource constrained projects involve cash flows occurring during their life cycle. Several recent studies consider the problem of scheduling projects to maximise the net present value (NPV) of these cash flows. Their basic common assumption is that cash flows are mainly associated with specific events and they occur at event realisation times. An alternative assumption, which can be more realistic, is that cash inflows occur periodically, for example every month, as progress payments. This article considers the problem of maximising NPV given the alternative assumption. Three different heuristic rules are developed. The performance of these heuristic rules is analysed through a full factorial experiment with 108 scheduling conditions. The results indicate that three rules provide near-optimal schedules with respect to NPV maximisation while producing time schedules that do not delay the project completion time extensively. 相似文献
19.
J N D Gupta A J Ruiz-torres S Webster 《The Journal of the Operational Research Society》2003,54(12):1263-1274
This paper considers the problems of scheduling jobs on parallel identical machines where an optimal schedule is defined as one that gives the smallest maximum tardiness (or the minimum number of tardy jobs) among the set of schedules with optimal total flow-time (the sum of the completion times of all jobs). We show that these problems are unary NP-Hard, develop lower bounds for these two secondary criteria problems, and describe heuristic algorithms for their solution. Results of a computational study show that the proposed heuristic algorithms are quite effective and efficient in solving these hierarchical criteria scheduling problems. 相似文献
20.
Hyper-heuristics or “methodologies to choose heuristics” are becoming increasingly popular given their suitability to solve
hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics
or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are
represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto
machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously
sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules
and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of
NSGA-II when handling multi-objective problems. 相似文献