Equivalence of mean flow time problems and mean absolute deviation problems

doi:10.1016/0167-6377(90)90056-B

Operations Research Letters

Volume 9, Issue 6, November 1990, Pages 371-374

https://doi.org/10.1016/0167-6377(90)90056-B Get rights and content

Abstract

The mean flow time problem and the mean absolute deviation problem for multiple uniform parallel machines are shown to be equivalent. For multiple unrelated parallel machines, a reduction of the mean absolute deviation problem into a transportation problem is presented.

References (10)

U. Bagchi et al.
Minimizing mean absolute deviation of completion times about a common due date
Naval Res. Logist. Quart.
(1986)
J. Bruno et al.
Scheduling independent tasks to reduce mean finishing time
Comm. of the ACM
(1974)
H. Emmons
Scheduling to a common due date on parallel uniform processors
Naval Res. Logist. Quart.
(1987)
M.R. Garey et al.
One-processor scheduling with symmetric earliness and tardiness penalties
Math. Oper. Res.
(1988)

There are more references available in the full text version of this article.

Cited by (28)

A multi-agent system for the weighted earliness tardiness parallel machine problem
2014, Computers and Operations Research
This paper studies the weighted earliness tardiness parallel machine problem where jobs have different processing times and distinct due dates. This NP hard problem arises in most just-in-time production environments. It is herein modeled as a mixed integer program, and solved using MAS^H, a deterministic heuristic based on multi-agent systems. MAS^H has three types of agents: I, G, and M. The I-agents are free jobs that need to be scheduled, whereas the G-agents are groups of jobs already assigned to machines. The M-agent acts as the system's manager of the independent intelligent I- and G-agents, which are driven by their own goals, fitness assessments, and context-dependent decision rules. The I- and G-agents employ exact and approximate approaches as part of their decisional process while the M-agent uses local search mechanisms to improve their (partial) solutions. The design of MAS^H is innovative in the way its intelligent agents determine bottleneck clusters and resolve conflicts for time slots. The numerical results provide computational evidence of the efficiency of MAS^H, whose performance on benchmark instances from the literature is superior to that of existing approaches. The success of MAS^H and its modularity make it a viable alternative to more complex manufacturing problems. Most importantly, they demonstrate the benefits of the hybridization of artificial intelligence and operations research.
Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs
2012, Computers and Operations Research
Citation Excerpt :
Emmons [9] presents an O(n log n) algorithm to solve the Q|dj=d|Σ(αEj+βTj) problem. An O(n3) algorithm for the R|dj=d|Σ(Ej+Tj) problem is due to Alidaee and Panwalkar [10] and Kubiak et al. [11]. The two-machine version of the problem we solve herein was dealt with by Mosheiov and Sarig [1], who provide a constant-time algorithm.
We consider a problem of scheduling n identical nonpreemptive jobs with a common due date on m uniform parallel machines. The objective is to determine an optimal value of the due date and an optimal allocation of jobs onto machines so as to minimize a total cost function, which is the function of earliness, tardiness and due date values. For the problem under study, we establish a set of properties of an optimal solution and suggest a two-phase algorithm to tackle the problem. First, we limit the number of due dates one needs to consider in pursuit of optimality. Next, we provide a polynomial-time algorithm to build an optimal schedule for a fixed due date. The key result is an O(m² log m) algorithm that solves the main problem to optimality.
Scope and purpose: To extend the existing research on cost minimization with earliness, tardiness and due date penalties to the case of uniform parallel machines.
Due-date assignment on uniform machines
2009, European Journal of Operational Research
The classical weighted minsum scheduling and due-date assignment problem (with earliness, tardiness and due-date costs) was shown to be polynomially solvable on a single machine, more than two decades ago. Later, it was shown to have a polynomial time solution in the case of identical processing time jobs and parallel identical machines. We extend the latter setting to parallel uniform machines. We show that the two-machine case is solved in constant time. Furthermore, the problem remains polynomially solvable for a given (fixed) number of machines.
Analysis and algorithms for coordinated scheduling of parallel machine manufacturing and 3PL transportation
2008, International Journal of Production Economics
Nowadays, it is popular to outsource transportation and distribution of finished products to third-party logistics (3PL) providers in many industries. In order to shorten the response time from order receipt to delivery, and also to improve on-time delivery accuracy, the decision of manufacturing scheduling and transportation scheduling should consider the constraints between manufacturing and transportation. In this paper, we study a coordinated scheduling problem of parallel machine assembly manufacturing and multi-destination transportation in the make-to-order (MTO) consumer electronics supply chain (CESC). By considering the constraints between parallel machine assembly and 3PL transportation, the overall problem is decomposed into a parallel machine scheduling sub-problem and a 3PL transportation sub-problem. The 3PL transportation problem is proved to be NP-complete. Heuristic algorithms are proposed to solve the parallel machine assembly scheduling problem.
Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain
2008, European Journal of Operational Research
Citation Excerpt :
A review of the literature indicates that only a few of the published articles on earliness and tardiness (E/T) address the problem of scheduling jobs on multiple, non-identical parallel machines to minimize the total penalty costs for earliness and tardiness (Zhu and Heady, 2000). A set of work consider common due date (e.g., Emmons, 1987; Kubiak et al., 1990; Bank and Werner, 2001). Lauff and Werner (2004) reviewed related literature in detail. Another set of work considers distinct due dates (e.g., Heady and Zhu, 1998; Zhu and Heady, 2000; Della Croce and Trubian, 2002).
In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.
Exponential neighborhood search for a parallel machine scheduling problem
2008, Computers and Operations Research
We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution of this paper is to propose a pseudo-polynomial algorithm that finds the best solution of the exponential neighborhood. Additionally, we present some computational results.

View all citing articles on Scopus

View full text

Equivalence of mean flow time problems and mean absolute deviation problems

Abstract

Minimizing mean absolute deviation of completion times about a common due date

Naval Res. Logist. Quart.

Scheduling independent tasks to reduce mean finishing time

Comm. of the ACM

Scheduling to a common due date on parallel uniform processors

Naval Res. Logist. Quart.

One-processor scheduling with symmetric earliness and tardiness penalties

Math. Oper. Res.