Scheduling jobs on unrelated parallel machines to minimize regular total cost functions

Date

1999-02-01

Author

Azizoğlu, Meral
Kirca, O

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

227
views

0
downloads

In this paper we consider unrelated parallel machine scheduling problems that involve the minimization of regular total cost functions. We first present some properties of optimal solutions and then provide a lower bound. These mechanisms are tested on the well-known practical problem of minimizing total weighted flow time on unrelated parallel machines. In doing so, we design a branch and bound algorithm incorporating the mechanisms derived for the general total cost function along with the ones derived specifically for the total weighted flow time criterion. Computational experience indicates that incorporating reduction and bounding mechanisms significantly improves the performance of the branch and bound algorithm.

Subject Keywords

Time

URI

https://hdl.handle.net/11511/33382

Journal

IIE TRANSACTIONS

DOI

https://doi.org/10.1023/a:1007516602473

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Scheduling a batch processing machine with non-identical job sizes Azizoğlu, Meral (2000-07-10) The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with arbitrary job processing times, job weights and job sizes. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to similar to 25 jobs in reasonable C...
Scheduling a batch processing machine with incompatible job families Azizoğlu, Meral (2001-04-01) The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with incompatible job families. Jobs in a given family have identical job processing times, arbitrary job weights, and arbitrary job sizes. Batches are limited to jobs from the same family. The scheduling objective is to minimize total weighted...
Scheduling job families about an unrestricted common due date on a single machine Azizoğlu, Meral (1997-01-01) We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due date to minimize total weighted earliness and tardiness cost. Jobs are grouped into families where jobs in the same family share a setup; a setup time is required between the processing of two jobs from different families. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. These rates are assessed on a per-period basis when the completion time deviates from its ...
Uniform Parallel machine scheduling with family set-up times Tamer, Meral; Azizoğlu, Meral; Azizoğlu, Meral; Department of Industrial Engineering (2003) In this study, we address the scheduling problem of uniform parallel machines with family set-up times so as to minimize the total completion time. We develop a branch and jound algorithm that employs an efficient branching scheme. A bounding mechanism is jroposed to increase the efficiency of this algorithm. Our computational experiment shows hat the optimal solution is found in reasonable CPU times up to 15 jobs. Further experiments »re conducted to test the bounding mechanisms and this experiment indicat...
Preemptive scheduling on identical parallel machines subject to deadlines Azizoğlu, Meral (2003-07-01) We consider the problem of scheduling n preemptive jobs with deadlines on in identical parallel machines so as to minimize total completion time. We show that the problem is polynomially solvable when the processing times and deadlines are agreeable.

Citation Formats

M. Azizoğlu and O. Kirca, “Scheduling jobs on unrelated parallel machines to minimize regular total cost functions,” IIE TRANSACTIONS, pp. 153–159, 1999, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/33382.