Premium
Simultaneous optimization of efficiency and performance balance measures in single‐machine scheduling problems
Author(s) -
Federgruen Awi,
Mosheiov Gur
Publication year - 1993
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199312)40:7<951::aid-nav3220400707>3.0.co;2-1
Subject(s) - single machine scheduling , computer science , scheduling (production processes) , balance (ability) , mathematical optimization , operations research , job shop scheduling , mathematics , operating system , schedule , medicine , physical medicine and rehabilitation
Manufacturing and service organizations routinely face the challenge of scheduling jobs, orders, or individual customers in a schedule that optimizes either (i) an aggregate efficiency measure, (ii) a measure of performance balance , or (iii) some combination of these two objectives. We address these questions for single‐machine job scheduling systems with fixed or controllable due dates. We show that a large class of such problems can be optimized by solving either a single instance or a finite sequence of instances of the so‐called (SQC) problem, in which the sum of general quasiconvex functions of the jobs' completion times is to be minimized. To solve a single instance of (SQC), we develop an efficient, though pseudopolynomial algorithm, based on dynamic programming. The algorithm generates a solution that is optimal among all schedules whose starting time is restricted to the points of a prespecified (arbitrary) grid. The algorithm is embedded in an iterative procedure, where in each iteration a specific instance of (SQC) is solved. Special attention is given to the simultaneous minimization of the mean and variance of completion times. © 1993 John Wiley & Sons, Inc.