Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1107.90022
Mosheiov, Gur; Oron, Daniel
Minmax scheduling with job-classes and earliness-tardiness costs. (English)
[J] Eur. J. Oper. Res. 177, No. 1, 612-622 (2007). ISSN 0377-2217

Summary: We address scheduling problems with job-dependent due-dates and general (possibly nonlinear and asymmetric) earliness and tardiness costs. The number of distinct due-dates is substantially smaller than the number of jobs, thus jobs are partitioned to classes, where all jobs of a given class share a common due-date. We consider the settings of a single machine and parallel identical machines. Our objective is of a minmax type, i.e., we seek a schedule that minimizes the maximum earliness/tardiness cost among all jobs.We introduce a nonlinear program that needs to be solved in order to obtain an optimal solution for the single-machine case. The case of parallel identical machines is NP-hard even for two machines, linear costs and a single common due-date. We introduce an LPT-based (largest processing time first) heuristic and a simple lower bound on the optimal cost. Both the heuristic and the lower bound are asymptotically accurate under very general conditions. Our numerical tests indicate that the heuristic produces very close-to-optimal schedules in all settings.

MSC 2000:: *90B35 Scheduling theory

Keywords: scheduling; earliness-tardiness cost; parallel machines; minmax

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]