1,721,031 research outputs found
Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times
No full textThe problem of makespan minimization in a flow shop with two-machines when the input buffer of the second machine can only host a limited number c of parts is known to be NP-hard for any c>0 and c⩽n, where n is the number of jobs. In this paper we analyze this problem in the context of batch scheduling, i.e. when identical parts must be processed consecutively. In particular we study the case in which each batch requires sequence independent setup times and removal times. We then show that, if the size of the ith batch is larger than a value b*_i, then the makespan minimization problem can be formulated as a special case of TSP and solved in polynomial time. The cost structure of this TSP can be reduced to the one defined for the two-machine no-wait flow shop. Hence, we give a closed form expression for b*_i. Then, we prove that when the same algorithm is applied to batch sizes smaller than b*_i, the error goes to zero as the batch sizes approach the values b*_i
Sequencing two classes of jobs on a machine with an external no-idle constraint
No full textIn this paper, we deal with a special type of scheduling problem. There are two classes of jobs to be processed on a single machine. Jobs of class A are directly delivered to the customers and we want to minimise their total flow time. Jobs of class B do not contribute to the objective function but must respect a no-idle constraint (i.e. they are required to keep an external downstream machine busy). This problem arises in some real-world production environments where the downstream process must not be interrupted because of technological constraints, economic viability or because the firm is bound to keep the external process continuously active (e.g. a contract with a downstream firm imposing penalties if the supply is interrupted). We prove that the general problem is NP-Hard. We introduce two mathematical programming-based approaches and some constructive heuristics. The various approaches are compared on the basis of a large computational campaign
The effectiveness of static implications in real-time railway traffic management
No full textWe study a real-time railway traffic management problem. It consists in adjusting train timetables in order to restore feasibility when unforeseen events in the network make unfeasible the off-line generated timetable. The problem can be formulated as a huge job-shop problem with blocking constraints, which has to be solved within strict time limits due to real-time constraints. Unfortunately, even finding a feasible solution is an NP-complete problem. To this aim, implication rules are a powerful tool to design fast and effective solution algorithms. In this paper we present a new simple static implication rule for the blocking job-shop problem, and its application to the real-time railway traffic management problem. A computational experience, based on a real railway infrastructure, shows the effectiveness of the implication rule to speed up a heuristic solution algorithm.Transport and PlanningCivil Engineering and Geoscience
An analytical model for thread-core mapping for tiled CMPs
No full textModern computing chips are composed of multiple, simple, low-power processing cores. Increasing the number of processing cores in a single chip brings the opportunity to exploit the inherent massive level of thread parallelism and further improved performance. However, efficient allocation of applications (threads) to available cores is a complicated process. Failing to do so, the mapping can be the limiting factor for achieving better performance on a tiled chip-multiprocessor (CMP). In this paper, we propose a mathematical formulation based on mixed integer linear program (MILP) to map application threads on cores at worst-case scenario by keeping into account the spatial topology of a two-dimensional mesh (2D-mesh) Networks-on-Chip (NoC). Our model allows evaluating in absolute term the performance of different mapping and routing algorithms. The proposed analytical model is general enough to consider a different optimising policy from energy to latency and a different number of memory controllers. In the experiments, we have shown that the proposed approach can achieve up to 40% reduction over the traditional zig-zag heuristic, therefore showing that there is a range for improving application mapping
An Advanced Real-Time Train Dispatching System for Minimizing the Propagation of Delays in a Dispatching Area Under Severe Disturbances
No full textDSS, Delay management, Short-term train scheduling, Temporal decomposition,
A branch and bound algorithm for scheduling trains in a rail network
No full textThe paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits
A New Class of Greedy Heuristics for Job Shop Scheduling Problems
No full textIn this paper we introduce a new class of greedy heuristics for general job shop scheduling problems. In particular we deal with the classical job shop, i.e. with unlimited capacity buffer, and job shop problems with blocking and no-wait. The proposed algorithm family is a simple randomized greedy family based on a general formulation of the job shop problem. We report on an extensive study of the proposed algorithms, and comparisons with other greedy algorithms axe presente
- …
