1,721,072 research outputs found
No-Wait Flow Shop Scheduling with Large Lot Sizes
No full textNO-WAIT FLOW SHOP consists of minimizing the completion time of a set of N parts that must undergo a series of m machines in the same order, with the constraint that each part, once started, cannot wait on or between the machines. The problem is known to be NP-complete for m ≥ 3, while an O(N log N) algorithm exists when m = 2. In this paper, some new results are presented concerning the case in which parts are grouped into lots of identical parts. An ε-approximate algorithm is proposed, based on the solution to a transportation problem. The relative error of the approximation goes to zero as the size of any lot grows. Experimental results are reported comparing our approach with the only other ε-approximate algorithm known in literature
Planning the Routing Mix in FASs to Minimize Total Transportation Time
No full textThe routing mix problem in flexible assembly systems is considered. The problem consists of assigning the operations for each part to the machines, with the two objectives of balancing the machine workloads and minimizing the burden of the transportation system. These two objectives are sometimes conflicting, since the latter tends to support assigning operations to the same machine(s) as much as possible, and this may be bad for workload balancing. A linear programming problem is presented that, given a constraint on the workload of each machine, finds one solution that minimizes the overall time spent moving the parts from one machine to another. Since such a linear program may have an exponential number of variables, an efficient column generation technique to solve the problem is devised. The efficiency of the method is validated by experiments on a large number of random problems
Scheduling no-wait robotic cells with two and three machines
No full textA no-wait robotic cell is an automated m-machine flow shop in which one robot is used to move the parts from a machine to the next, as well as between the machines and the input/output devices. Parts are not allowed to wait, either on a machine or on the robot. The problem is to sequence the parts and, concurrently, schedule the robot moves in order to maximize productivity. In the two-machine case, we show that the problem is solvable in time O(n log n) by reducing it to the classical two-machines no-wait flow shop. For the three-machine case and identical parts, it is shown that it is sufficient to consider robot move cycles in which all the machines are visited once or twice. (C) 2000 Elsevier Science B.V. All rights reserved
Scheduling with job-rejection and position-dependent processing times on proportionate flowshops
No full textWe study the classical scheduling problem of minimizing makespan on a proportionate flowshop. Position-dependent job processing times in the most general way are considered. We introduce a polynomial time solution procedure which is more efficient than the one known in the literature. The problem is further extended to allow job-rejection. This more general version is shown to be solved in polynomial time as well
Optimal Assignment of High Multiplicity Flight Plans to Dispatchers
No full textThis paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP-complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently solution a set of real-life instances
Specialized Inspection Problems in Serial Production Systems
No full textWhen defects are sometimes introduced in a serial manufacturing system, objectives such as minimization of total
'cost', maximization of yield, and minimization of undetected faulty units are all viable optimization objectives. We
take a comprehensive look at the inspection problems in this setting and develop several new models for locating
specialized inspection stations, stations which can only detect defects produced by specific operations. We consider
the cases (1) when inspection/rework stations are to be located, (2) when inspection stations are already located but
their operating modes (rework or scrap) are to be determined, and (3) when both locations and operating modes are
to be determined. We discuss exact and/or heuristic methods of solutions for these models, and present some
computational experience
The list scheduling algorithm for scheduling unreliable jobs on two parallel machines
No full textIn this paper, we study a scheduling problem with unreliable jobs. Each job is characterized by a success probability and by a reward earned in case of success. In case of failure, the job blocks the machine that is processing it, and the jobs subsequently sequenced on that machine cannot be performed. The objective function is to maximize the expected reward. We address the problem in the case of two parallel machines, and analyze the worst-case performance of a simple list scheduling algorithm. We show that the algorithm provides an approximation ratio of (2 + sqrt(2)) / 4 ≃ 0, 853, and that the bound is tight. We also provide a complexity result concerning the related Total Weighted Discounted Completion Time Problem on parallel machines
Computing the Nash Solutions for Scheduling Bargaining Problems
No full textIn this paper we focus on the Nash Bargaining Solution (NBS) in a scheduling scenario with two players. The problem is shown to be NP-hard, but an effective computing scheme for finding NBS is presented. Extensive computational results are provided, showing that NBS can always be found within reasonable computation time
The Inspection Station Location Problem in Hazardous Material Transportation: Some Heuristics and Bounds
No full text- …
