共查询到20条相似文献,搜索用时 31 毫秒
1.
We address a single-machine batch scheduling problem to minimize total flow time. Processing times are assumed to be identical for all jobs. Setup times are assumed to be identical for all batches. As in many practical situations, batch sizes may be bounded. In the first setting studied in this paper, all batch sizes cannot exceed a common upper bound. In the second setting, all batch sizes share a common lower bound. An optimal solution consists of the number of batches and their (integer) size. We introduce an efficient solution for both problems. 相似文献
2.
3.
4.
Zizhen Zhang Oscar Che Brenda Cheang Andrew Lim Hu Qin 《European Journal of Operational Research》2013
In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers. 相似文献
5.
A single machine scheduling problem with availability constraints and sequence-dependent setup costs
Francisco Ángel-Bello Ada Álvarez Joaquín Pacheco Iris Martínez 《Applied Mathematical Modelling》2011
We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic. 相似文献
6.
Hanen Akrout Bassem Jarboui Patrick Siarry Abdelwaheb Reba? 《Computational Optimization and Applications》2012,51(1):411-435
When handling combinatorial optimization problems, we try to get the optimal arrangement of discrete entities so that the
requirements and the constraints are satisfied. These problems become more and more important in various industrial and academic
fields. So, over the past years, several techniques have been proposed to solve them. In this paper, we are interested in
the single machine scheduling problem with Sequence-Dependent Setup Times, which can be solved through different approaches.
We present a hybrid algorithm which combines Greedy Randomized Adaptive Search Procedure and Differential Evolution for tackling
this problem. Our algorithm is tested on benchmark instances from the literature. The computational experiments prove the
efficiency of this algorithm. 相似文献
7.
8.
Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements 总被引:1,自引:0,他引:1
We consider the resource-constrained scheduling problem when each job’s resource requirements remain constant over its processing time. We study a time-indexed formulation of the problem, providing facet-defining inequalities for a projection of the resulting polyhedron that exploit the resource limitations inherent in the problem. Lifting procedures are then provided for obtaining strong valid inequalities for the original polyhedron. Computational results are presented to demonstrate the strength of these inequalities. 相似文献
9.
W J Chen 《The Journal of the Operational Research Society》2006,57(4):410-415
This paper deals with a single-machine scheduling problem with limited machine availability. The limited availability of machine results from periodic maintenance activities. In our research, a periodic maintenance schedule consists of several maintenance periods. Each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the total flow time subject to periodic maintenance and nonresumable jobs. Some important theorems are proved for the problem. A branch-and-bound algorithm that utilizes several theorems is proposed to find the optimal schedule. We also develop a heuristic to solve large sized problems. In this paper, computational results show that the proposed heuristic is highly accurate and efficient. 相似文献
10.
The importance of the role that learning plays in manufacturing, industry and computer systems is undeniable as well as the profit that can be increased if this phenomenon is taken into consideration for short- and long-term optimization. In this paper, we focus on scheduling jobs on a single processor, where its effectiveness can increase with the number of processed jobs, to minimize one of the following objectives: the maximum completion time with the release dates, the maximum lateness and the number of late jobs. It is proved that these well known polynomially solvable problems become at least NP-hard with the considered learning models. To solve them we provide some elimination procedures that are used to construct a branch and bound algorithm. Furthermore, we propose some fast heuristics for the problem of minimizing the number of late jobs with the general model of the learning effect. 相似文献
11.
《European Journal of Operational Research》2001,132(1):224-242
In this paper, a new memetic algorithm (MA) for the total tardiness single machine scheduling (SMS) problem with due dates and sequence-dependent setup times is proposed. The main contributions with respect to the implementation of the hybrid population approach are a hierarchically structured population conceived as a ternary tree and the evaluation of three recombination operators. Concerning the local improvement procedure, several neighborhood reduction schemes are developed and proved to be effective when compared to the complete neighborhood. Results of computational experiments are reported for a set of randomly generated test problems. The memetic approach and a pure genetic algorithm (GA) version are compared with a multiple start algorithm that employs the all-pairs neighborhood as well as two constructive heuristics. 相似文献
12.
This paper gives an O(n√nlog3n) time algorithm for the chance-constrained sequencing problem on a single machine, where n is the number of jobs and the objective is to minimize the number of jobs which are early with probability not smaller than α (a given constant) against the common due time d. 相似文献
13.
在单机供应链排序问题中, 机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何 安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小. 对于工件加工可恢复的情况,可在多项式时间 O(n^2) 内得到最优序. 对于工件加工不可恢复的情况,证明了问题是强NP-难的, 并提出了~2-近似算法. 相似文献
14.
It is discussed hown railway routes arriving regularly at some station should be scheduled to minimize the maximum waiting time for passengers changing trains.
Zusammenfassung In der Arbeit wird untersucht, wie man fürn Eisenbahnlinien, die in regelmä\igen Abständen in einem Bahnhof eintreffen, die optimale Reihenfolge erhält, so da\ die maximale Wartezeit für die Reisenden, die in den Zug einer anderen Linie umsteigen wollen, minimiert wird.相似文献
15.
F Della Croce R Tadei P Baracco A Grosso 《The Journal of the Operational Research Society》1998,49(10):1101-1106
This paper deals with the single machine total tardiness problem. From Emmons’ basic dominance conditions a new partition theorem is derived which generalises Lawler’s decomposition rule and leads to a new double decomposition procedure. This procedure is embedded into a branch and bound method which applies a new lower bound based on due dates reassignment. The branch and bound method is tested on problems with size up to 150 jobs. 相似文献
16.
We consider an on-line list scheduling problem of multi-core processor tasks with virtualization to minimize makespan. The competitive ratio of an on-line algorithm is shown for every specific m, where m is the number of processors. Better on-line algorithms are presented for a small number of processors. 相似文献
17.
Alexey Soloviev Hongwei Gao 《Moscow University Computational Mathematics and Cybernetics》2016,40(3):110-113
A multiperiod version of the Markowitz optimization problem is considered by assuming that the financial market model is discrete with respect to time and the number of scenarios. Basing on the optimal strategy of securities trading, we find the upper bound of the expected final portfolio value which does not lead to bankruptcy. 相似文献
18.
Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance 总被引:1,自引:0,他引:1
This paper deals with a single machine scheduling problems with availability constraints. The unavailability of machine results from periodic maintenance activities. In our research, a periodic maintenance consists of several maintenance periods. We consider a machine should stop to maintain after a periodic time interval or to change tools after a fixed amount of jobs processed simultaneously. Each maintenance period is scheduled after a periodic time interval. We study the problems under deterministic environment and flexible maintenance considerations. Preemptive operation is not allowed. In addition, we propose a more reasonable flexible model for the real production settings. The objective is to minimize the makespan. The proposed problem is NP-hard in the strong sense and some heuristic algorithms are provided. The purpose is to present an efficient and effective heuristic algorithm so that it will be straightforward and easy to implement. Computational results show that the proposed algorithm first fit decreasing (DFF) performs well. 相似文献
19.
R Rudek 《The Journal of the Operational Research Society》2014,65(8):1170-1176
In this paper, we analyse the single processor maximum completion time (makespan) minimization problem with distinct release dates of jobs and the sum-of-processing time-based learning effect. We prove that the considered problem is strongly NP-hard, if, in addition to jobs with the same learning ratio, there are jobs with constant job processing times. Such jobs are not affected by learning and model, for instance, required system upgrades or training courses. 相似文献
20.
The conventional Maximum flow problem is modified to take account of possible requirements at intermediate nodes across which flow takes place. This is achieved by incorporating pseudo or priority arcs to act as thresholds controlling out-flow from the nodes and modifying the Ford and Fulkerson algorithm to take account of these thresholds. Effect of introducing these threshold-requirements at intermediate nodes on the final flow into the sink in the network is examined by some numerical examples. 相似文献