共查询到20条相似文献,搜索用时 0 毫秒
1.
Zoltán Blázsik Csanád Imreh Zoltán Kovács 《Central European Journal of Operations Research》2008,16(4):379-390
In this work we present a new scheduling model for parallel machines, which extends the multiprocessor scheduling problem
with release times for minimizing the total tardiness, and also extends the problem of vehicle routing with time windows.
This new model is motivated by a resource allocation problem, which appears in the service sector. We present two class of
heuristic algorithms for the solution of the problem, the first class is a class of greedy algorithms, the second class is
based on the solutions of linear assignment problems. Furthermore we give a rescheduling algorithm, which improves a given
feasible solution of the problem.
This research has been supported by the Hungarian National Foundation for Scientific Research, Grant T046405. 相似文献
2.
Carlo Filippi 《Operations Research Letters》2010,38(4):312-317
We consider a high-multiplicity parallel machine scheduling problem where the objective is to minimize the weighted sum of completion times. We suggest an approximate algorithm and we prove that it is asymptotically exact. The algorithm exploits a convex quadratic relaxation of the problem to fix a partial schedule, consisting of most jobs, and then assigns the residual jobs following a simple and general rule. The quality of the obtained solution is evidenced by some numerical tests. 相似文献
3.
In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem. 相似文献
4.
Fabrice Tercinet Emmanuel Néron Christophe Lenté 《4OR: A Quarterly Journal of Operations Research》2006,4(4):297-317
This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r
i
, q
i
|C
max. The link between P||C
max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r
i
, q
i
|C
max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported. 相似文献
5.
《European Journal of Operational Research》1999,116(1):220-232
We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time. 相似文献
6.
A heuristic algorithm is described for vehicle routing and scheduling problems to minimise the total travel time, where the time required for a vehicle to travel along any road in the network varies according to the time of travel. The variation is caused by congestion that is typically greatest during morning and evening rush hours. The algorithm is used to schedule a fleet of delivery vehicles operating in the South West of the United Kingdom for a sample of days. The results demonstrate how conventional methods that do not take time-varying speeds into account when planning, except for an overall contingency allowance, may still lead to some routes taking too long. The results are analysed to show that in the case study using the proposed approach can lead to savings in CO2 emissions of about 7%. 相似文献
7.
Mauro Dell’Amico Manuel Iori Silvano Martello Michele Monaci 《Journal of Heuristics》2012,18(6):939-942
A recent paper (Davidovi? et al., J. Heuristics, 18:549?C569, 2012) presented a bee colony metaheuristic for scheduling independent tasks to identical processors, evaluating its performance on a benchmark set of instances from the literature. We examine two exact algorithms from the literature, the former published in 1995, the latter in 2008 (and not cited by the authors). We show that both such algorithms solve to proven optimality all the considered instances in a computing time that is several orders of magnitude smaller than the time taken by the new algorithm to produce an approximate solution. 相似文献
8.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ 台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$ 为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$ 为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$ 时, 该算法近似比为3, 当接受工件个数小于$(m-1)$ 时, 该算法近似比为$(2+\rho)$ , 其中$\rho$ 为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。 相似文献
9.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ 台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$ 为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$ 为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$ 时, 该算法近似比为3, 当接受工件个数小于$(m-1)$ 时, 该算法近似比为$(2+\rho)$ , 其中$\rho$ 为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。 相似文献
10.
In studies on scheduling problems, generally setup times and removal times of jobs have been neglected or by including those into processing times. However, in some production systems, setup times and removal times are very important such that they should be considered independent from processing times. Since, in general jobs are done according to automatic machine processes in production systems processing times do not differ according to process sequence. But, since human factor becomes influential when setup times and removal times are taken into consideration, setup times will be decreasing by repeating setup processes frequently. This fact is defined with learning effect in scheduling literature. In this study, a bicriteria m-identical parallel machines scheduling problem with a learning effect of setup times and removal times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. A mathematical programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 15 jobs and five machines. We also proposed three heuristic approaches for solving large jobs problems. According to the best of our knowledge, no work exists on the minimization of the weighted sum of total completion time and total tardiness with a learning effect of setup times and removal times. 相似文献
11.
This paper describes an application of genetic algorithms to the bus driver scheduling problem. The application of genetic algorithms extends the traditional approach of Set Covering/Set Partitioning formulations, allowing the simultaneous consideration of several complex criteria. The genetic algorithm is integrated in a DSS but can be used as a very interactive tool or a stand-alone application. It incorporates the user's knowledge in a quite natural way and produces solutions that are almost directly implemented by the transport companies in their operational planning processes. Computational results with airline and bus crew scheduling problems from real world companies are presented and discussed. 相似文献
12.
Fabrizio Marinelli Maria Elena Nenni Antonio Sforza 《Annals of Operations Research》2007,150(1):177-192
The aim of this work is to propose a solution approach for a capacitated lot sizing and scheduling real problem with parallel
machines and shared buffers, arising in a packaging company producing yoghurt. The problem has been formulated as a hybrid
Continuous Set-up and Capacitated Lot Sizing Problem (CSLP–CLSP). A new effective two stage optimisation heuristic based on
the decomposition of the problem into a lot sizing problem and a scheduling problem has been developed. An assignment of mixture
to buffers is made in the first stage, and therefore the corresponding orders are scheduled on the production lines by performing
a local search. Computational tests have been performed on the real data provided by the company. The heuristic exhibits near-optimal
solutions, all obtained in a very short computational time. 相似文献
13.
N Safaei D Banjevic A K S Jardine 《The Journal of the Operational Research Society》2011,62(6):1005-1018
In this paper, a real maintenance workforce-constrained scheduling problem is formulated as a bi-objective mixed-integer programming model with the aim of simultaneously minimizing the workforce requirements and maximizing the equipment availability. The skilled workforce is provided by internal and external resources using regular time, overtime and contracting. The equipment availability is measured by the downtime required for preventive maintenance (scheduled) and failure repair (unscheduled) jobs. We also encounter imminent or potential failures whose priorities depend on the severity of the failure on the system (secondary failure). The total weighted flow time is used as a scheduling criterion to measure the equipment availability; the weight of each job directly depends on the expected downtime resulting from the associated failure. The proposed model is verified using two comprehensive numerical examples and some sensitivity analyses. We conclude by discussing the results. 相似文献
14.
J V Caixeta-Filho 《The Journal of the Operational Research Society》2006,57(6):637-642
The competitiveness of Brazil's citrus sector is a function of quality control in the transformation of fruit into juice. The transformation process commences with the harvest, the timing of which significantly affects fruit quality. In this paper, a mathematical model is formulated that links pertinent chemical, biologic, and logistic restrictions to the quality of the fruit to be harvested, applying linear programming theory. The modelling structure was verified and validated with real data from 320 Brazilian farms involved with an annual production of approximately 7?200?000 boxes of oranges. It could be attested that the maximization of the number of boxes of oranges to be harvested (strategy that is still adopted by a representative number of Brazilian citrus farmers, based on the industry advice) does not necessarily correspond to the maximum quantity of total soluble solids (TSS). In many cases, citrus harvested at the optimum TSS point offered higher concentrated juice productivity. The estimated potential benefits ($) from using the proposed model reached figures over 6%. 相似文献
15.
A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems
The problem of scheduling n jobs with known process times on m identical parallel machines with an objective of minimizing weighted flow time is NP-hard. However, when job weights are identical, it is well known that the problem is easily solved using the shortest processing time rule. In this paper, we show that a generalization of the shortest processing time rule minimizes weighted flow time in a class of problems where job weights are not identical. 相似文献
16.
The problem is related to a fleet of military aircraft with a certain flying program in which the availability of the aircraft
sufficient to meet the flying program is a challenging issue. During the pre- or after-flight inspections, some component
failures of the aircraft may be found. In such cases, the aircraft are sent to the repair shop to be scheduled for maintenance
jobs, consisting of failure repairs or preventive maintenance tasks. The objective is to schedule the jobs in such a way that
sufficient number of aircrafts is available for the next flight programs. The main resource, as well as the main constraint,
in the shop is skilled-workforce. The problem is formulated as a mixed-integer mathematical programming model in which the
network flow structure is used to simulate the flow of aircraft between missions, hanger and repair shop. The proposed model
is solved using the classical Branch-and-Bound method and its performance is verified and analyzed in terms of a number of
test problems adopted from the real data. The results empirically supported practical utility of the proposed model. 相似文献
17.
Gelders and Kleindorfer suggested a generalized detailed scheduling cost structure, based on the sum of weighted tardiness and weighted flowtime. They solved the single-machine scheduling problem using a transportation scheme to obtain lower bounds in their branch and bound approach. Recently, Fisher, Baker, Rinnooy Kan and Srinivasan reported attractive computation times with general algorithms adapted to the total tardiness problem for the single-machine case. In this paper four algorithms are adapted to the generalized cost structure mentioned above and extensive computational results are presented.This investigation shows that much is to be expected from the dual approach for more complex scheduling problems while dynamic programming deserves a new research effort because of its efficiency in special structured problems and/or problems where a posteriori precedence relations (dominance criteria) can be developed. 相似文献
18.
In this work a genetic algorithm is presented for the unrelated parallel machine scheduling problem in which machine and job sequence dependent setup times are considered. The proposed genetic algorithm includes a fast local search and a local search enhanced crossover operator. Two versions of the algorithm are obtained after extensive calibrations using the Design of Experiments (DOE) approach. We review, evaluate and compare the proposed algorithm against the best methods known from the literature. We also develop a benchmark of small and large instances to carry out the computational experiments. After an exhaustive computational and statistical analysis we can conclude that the proposed method shows an excellent performance overcoming the rest of the evaluated methods in a comprehensive benchmark set of instances. 相似文献
19.
《Mathematical and Computer Modelling》1996,23(7):45-57
The paper presents a multilevel decision model for simultaneous machine and vehicle scheduling in a flexible manufacturing system. The system is composed of various machine types and a set of automated guided vehicles that permit each part to move between any pair of machines. The upper level of the decision model involves machine loading and part routing for which a bicriterion integer formulation is presented with the objective of balancing machine workloads and intermachine flows of parts. The lower level involves simultaneous scheduling of machines and vehicles for which a period-by-period heuristic is proposed based on a family of complex dispatching rules. The scheduling objective is to meet all part type requirements in a minimum time. Computational examples are included to illustrate the approach proposed. 相似文献
20.
F. J. Rodriguez C. Blum C. García-Martínez M. Lozano 《Annals of Operations Research》2012,201(1):383-401
In this work, we tackle the problem of scheduling a set of jobs on a set of non-identical parallel machines with the goal of minimising the total weighted completion times. GRASP is a multi-start method that consists of two phases: a solution construction phase, which randomly constructs a greedy solution, and an improvement phase, which uses that solution as an initial starting point. In the last few years, the GRASP methodology has arisen as a prospective metaheuristic approach to find high-quality solutions for several difficult problems in reasonable computational times. With the aim of providing additional results and insights along this line of research, this paper proposes a new GRASP model that combines the basic scheme with two significant elements that have been shown to be very successful in order to improve GRASP performance. These elements are path-relinking and evolutionary path-relinking. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown. 相似文献