1,721,070 research outputs found
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 Largest-Z-ratio-First algorithm is 0.8531-approximate for scheduling unreliable jobs on m parallel machines
No full textIn this paper we analyze the worst-case performance of a greedy algorithm called Largest-Z-ratio-First for the problem of scheduling unreliable jobs on m parallel machines. Each job is characterized by a success probability and a reward earned in the case of success. In the case of failure, the jobs subsequently sequenced on that machine cannot be performed. The objective is to maximize the expected reward. We show the algorithm provides an approximation ratio of ≃0.853196, and that the bound is tight
Process selection and sequencing in a two-agents production system
No full textThis paper addresses a coordination problem concerning two production agents in a manufacturing system. The two agents have a set of processes which must be carried out on some common resource. They can use the resource individually,
but in general there may be an overall advantage in concurrently performing certain processes. The problem is to select concurrent processes and to sequence them with the aim of minimizing the total number of set-ups. In particular, a decomposition approach is proposed, in which first the concurrent processes are selected,
by solving a generalized network flow problem, and then an optimal process sequencing is efficiently found
Optimal Two-machine Scheduling in a Flexible Flow System
No full textA new approach to part type selection and scheduling of parts in a two-machine flexible flow line is presented. It consists of first selecting a small number of part types for simultaneous production, in suitable ratios, in order to balance the workloads among the machines, and then scheduling the parts of each batch in order to minimize both completion time as well as the maximum level of in-process inventory required. The system consists of two machines and all of the parts visit the two machines in the same order. Some advantages of the approach as presented here include management effectiveness and simplicity, in addition to other benefits inherent in a dynamic and flexible approach to part type selection (such as a higher utilization of the machines, a smoother tool changing activity, etc.)
Call planning in European pharmaceutical sales force management
No full textIn this paper, a mathematical model for the allocation of sales representatives is presented. The model takes into account some special features of pharmaceutical marketing, such as customer profiling (physicians), sales response functions and multi-product (drug) promotion procedures. The main peculiarity of the model is that it is suitable to those markets (such as European markets) where the detailed information about historical physician prescriptions is not available to pharmaceutical companies. A heuristic procedure has been designed and run to plan nationwide representative calls to more than 46000 physicians. A computational study, based on real data from a major pharmaceutical company, shows the feasibility of this algorithmic approach, resulting in significantly enhanced productivity. Moreover, the algorithm can be also employed as a tool to evaluate costly strategic options concerning sales force sizing and training
Polynomial algorithms for a two-class multiprocessor scheduling problem in mobile telecommunications systems
No full textThe problem of assigning information packets of different services to time slots of a radio frame is addressed. Packet sizes are divisible, and a maximum time slot to which a packet can be assigned is given.
We present a polynomial-time scheduling algorithm maximizing the number of scheduled packets
Set-up coordination between two stages of a supply chain
No full textIn the material flow of a plant, parts are processed in batches, each having two distinct attributes,
say shape and color. In one department, a set-up occurs every time the shape of the new batch is different
from the previous one. In a downstream department, there is a set-up when the color of the new batch is
different from the previous one. Since a unique sequence of batches must be established, the problem consists
in finding such a common sequence optimizing an overall utility index. Here we consider two indices,
namely the total number of set-ups and the maximum number of set-ups between the two departments. Both
problems are shown to be NP-hard. An efficient heuristic approach is presented for the first index which
allows to solve a set of real-life instances and performs satisfactorily on a large sample of experimental data
- …
