共查询到20条相似文献,搜索用时 15 毫秒
1.
公共交货期窗口下提前/拖期问题的多机调度算法 总被引:2,自引:1,他引:1
提出了求公共交货期窗口下提前/拖期都有惩罚的单机零件排序问题最优解的新算法,建立了相应多机零件排序问题的数学模型。在证明关于单机问题最优排序和最优公共交货期性质的若干定理的基础上,给出了求解多机问题的一个启发式算法。数值例子表明,该算法有较为理想的优化效果和工程实用价值。 相似文献
2.
This paper examines the problem of scheduling two-machine no-wait job shops to minimize makespan. The problem is known to be strongly NP-hard. A two-phase heuristic is developed to solve the problem. Phase 1 of the heuristic transforms the problem into a no-wait flow shop problem and solves it using the well known Gilmore and Gomory algorithm. Phase 2 of the heuristic improves the solution obtained in phase 1 using a simple tabu search algorithm. Computational results show that the proposed heuristic performs extremely well in terms of both solution quality and computation time. It finds an optimal solution to about 90% of the problem instances and the average deviation from the lower bond for the other problem instances is infinitesimal. 相似文献
3.
4.
Alain Guinet 《Journal of Intelligent Manufacturing》1995,6(2):95-103
The problem of scheduling N jobs on M uniform parallel machines is studied. The objective is to minimize the mean tardiness or the weighted sum of tardiness with weights based on jobs, on periods or both. For the mean tardiness criteria in the preemptive case, this problem is NP-hard but good solutions can be calculated with a transportation problem algorithm. In the nonpreemptive case the problem is therefore NP-hard, except for the cases with equal job processing times or with job due dates equal to job processing times. No dominant heuristic is known in the general nonpreemptive case. The author has developed a heuristic to solve the nonpreemptive scheduling problem with unrelated job processing times. Initially, the algorithm calculates a basic solution. Next, it considers the interchanges of job subsets to equal processing time sum interchanging resources (i.e. a machine for a given period). This paper models the scheduling problem. It presents the heuristic and its result quality, solving 576 problems for 18 problem sizes. An application of school timetable scheduling illustrates the use of this heuristic. 相似文献
5.
6.
José Fernando Gonçalves Mauricio G. C. Resende 《International Transactions in Operational Research》2014,21(2):215-246
This paper presents a local search, based on a new neighborhood for the job‐shop scheduling problem, and its application within a biased random‐key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based on an extension of the 1956 graphical method of Akers, is applied to improve the solution. The new heuristic is tested on a set of 205 standard instances taken from the job‐shop scheduling literature and compared with results obtained by other approaches. The new algorithm improved the best‐known solution values for 57 instances. 相似文献
7.
Fuh-Der Chou Tzu-Yun Chang Ching-En Lee 《International Transactions in Operational Research》2005,12(2):215-233
This paper attempts to solve a single machine‐scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem. 相似文献
8.
文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发式算法。它是基于反复的解决某些单机调度问题。然而在转换瓶颈算法中用Carlier算法解单机调度问题并不总能得到可行解,文中给出了一个反例证明了有产生不可行解的情况。另外,文章还以简洁的方法证明了转换瓶颈算法若用Schrage算法替代Carlier算法解单机调度问题不会产生不可行解。 相似文献
9.
We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%. 相似文献
10.
This paper investigates the problem of minimizing makespan on a single batch-processing machine, and the machine can process multiple jobs simultaneously. Each job is characterized by release time, processing time, and job size. We established a mixed integer programming model and proposed a valid lower bound for this problem. By introducing a definition of waste and idle space (WIS), this problem is proven to be equivalent to minimizing the WIS for the schedule. Since the problem is NP-hard, we proposed a heuristic and an ant colony optimization (ACO) algorithm based on the theorems presented. A candidate list strategy and a new method to construct heuristic information were introduced for the ACO approach to achieve a satisfactory solution in a reasonable computational time. Through extensive computational experiments, appropriate ACO parameter values were chosen and the effectiveness of the proposed algorithms was evaluated by solution quality and run time. The results showed that the ACO algorithm combined with the candidate list was more robust and consistently outperformed genetic algorithm (GA), CPLEX, and the other two heuristics, especially for large job instances. 相似文献
11.
This paper deals with a scheduling problem with machine maintenance in a textile company. In the production system, the sequence-dependent setup time of a job cannot be ignored when a switch between two different jobs occurs. This study presents a heuristic to minimize the completion time, or equivalently the total setup time subject to periodic maintenance and due dates. The performance of the heuristic is evaluated by comparing its solution with the solution of the branch-and-bound algorithm. The real data are used to demonstrate the effectiveness of the heuristic. 相似文献
12.
A no-wait job shop (NWJS) describes a situation where every job has its own processing sequence with the constraint that no waiting time is allowed between operations within any job. A NWJS problem with the objective of minimizing total completion time is a NP-hard problem and this paper proposes a hybrid genetic algorithm (HGA) to solve this complex problem. A genetic operation is defined by cutting out a section of genes from a chromosome and treated as a subproblem. This subproblem is then transformed into an asymmetric traveling salesman problem (ATSP) and solved with a heuristic algorithm. Subsequently, this section with new sequence is put back to replace the original section of chromosome. The incorporation of this problem-specific genetic operator is responsible for the hybrid adjective. By doing so, the course of the search of the proposed genetic algorithm is set to more profitable regions in the solution space. The experimental results show that this hybrid genetic algorithm can accelerate the convergence and improve solution quality as well. 相似文献
13.
This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent
setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between
two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed
outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function
of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective
function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently
finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the
branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution. 相似文献
14.
15.
Computational grids allow the sharing of geographically distributed computational resources in an efficient, reliable, and secure manner. Grid is still in its infancy, and there are many problems associated with the computational grid, namely job scheduling, resource management, information service, information security, routing, fault tolerance, and many more. Scheduling of jobs on grid nodes is an NP‐class problem warranting for heuristic and meta‐heuristic solution approach. In the proposed work, a meta‐heuristic technique, auto controlled ant colony optimization, has been applied to solve this problem. The work observes the effect of interprocess communication in process to optimize turnaround time of the job. The proposed model has been simulated in Matlab. For the different scenarios in computational grid, results have been analyzed. Result of the proposed model is compared with another meta‐heuristic technique genetic algorithm that has been applied for the same purpose. It is found that auto controlled ant colony optimization not only gives better solution in comparison to genetic algorithm, but also converges faster because initial solution itself is good because of constructive and decision‐based policy adapted by the former. Concurrency and Computation: Practice and Experience, 2012.© 2012 Wiley Periodicals, Inc. 相似文献
16.
《Computers & Industrial Engineering》2002,43(3):509-528
In this research the problem of scheduling n jobs to minimize the Total Weighted Late Work (TWLW) is evaluated within the single machine context. As the problem complexity increases, so does the solution complexity, and often the objective is to identify a heuristic or algorithm that may return a near optimal solution. Various scheduling rules, heuristics and algorithms, including the weighted shortest processing rule, a variation of the modified due date rule, a genetic algorithm, neighborhood job search, and space smoothing with neighborhood job search, are empirically evaluated using different parameters to determine the utility of each approach. 相似文献
17.
The problem of scheduling in two different types of flowshops (all jobs available at time zero, different job availability times known a priori) and in flowline-based manufacturing cells is considered with the objective of minimizing the sum of weighted flowtime and weighted tardiness of jobs. First, heuristic preference relations are developed by the consideration of lower bounds on the completion times, operation due-dates, and weights for holding and tardiness of jobs. A heuristic algorithm for scheduling is then proposed by making use of the heuristic preference relations. Two more heuristic algorithms are developed by implementing an improvement scheme to enhance the quality of the solution given by the first heuristic algorithm. The proposed and the existing heuristics are evaluated with respect to the three problem classes under consideration by solving 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 all three proposed heuristics perform better than the existing heuristics in giving a solution of superior quality and that the first proposed heuristic 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 existing heuristics, and also the effectiveness of heuristics based on simulated annealing. The results are discussed in detail. 相似文献
18.
Almost every computation task requires input data in order to find a solution. This is not a problem for a centralized system because data is usually available locally. However, in a parallel and distributed system, e.g., computation grids, the data may be in remote sites and must be transferred to the local site before the computation can proceed. As a result, the interleaved sequence of data transfer and job execution has a significant impact on the overall computational efficiency. In this paper, we analyze the computational complexity of the shared-data job scheduling problem on uniprocessor, with and without consideration of the storage capacity constraint on the local site.We show that if there is an upper bound on the server capacity, the problem is NP-complete, even when each job depends on at most two data items. For the case where there is no upper bound on the server capacity, we show that there exists an efficient algorithm that can provide an optimal job schedule when each job depends on at most two data items. We also propose an efficient heuristic algorithm that can determine good schedules for cases where there is no limit on the amount of data a job may access. The reported experiment results demonstrate that this heuristic algorithm performs very well, and derives near optimal solutions. 相似文献
19.
《Computers & Operations Research》2001,28(7):705-717
We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime. 相似文献
20.
The flow shop scheduling with blocking is considered an important scheduling problem which has many real-world applications. This paper proposes a new algorithm which applies heuristic techniques in harmony search algorithm (HSA) to minimize the total flow time. The proposed method is called modified harmony search algorithm with neighboring heuristics methods (MHSNH). To improve the initial harmony memory, we apply two heuristic techniques: nearest neighbor (NN) and constructive modified NEH (MNEH). A modified version of harmony search algorithm evolves to explore and generates a new solution. The newly generated solution is then enhanced by using neighboring heuristics. Lastly, another neighboring heuristic is applied to improve the obtained solution. The proposed algorithm is evaluated using 12 real-world problem instances each with 10 samples. The experimental evaluation is accomplished using two factors: CPU computational time and the number of iterations. For the first factor, comparative evaluation against six well-established methods shows that the proposed method achieves almost the best overall results in six problem instances out of the twelve and yields fruitful results for others. For the second factor, comparative evaluation against twelve well-regarded methods shows that the proposed method achieves the best overall results in three problem instances and obtains very good results in other instances. In a nutshell, the proposed MHSNH is an effective strategy for solving the job shop scheduling problem. 相似文献