Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed

Date

2003-06-01

Author

Azizoğlu, Meral
Koksalan, SK

Metadata

Show full item record

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

Item Usage Stats

217
views

0
downloads

We address the bicriteria problem of minimizing the number of tardy jobs and maximum earliness on a single machine where machine idle time is allowed. We show that the problem of minimizing the number of tardy jobs while maximum earliness is kept at its minimum value of zero is polynomially solvable. We present polynomial time algorithms for the maximum earliness problem subject to no tardy jobs and the maximum earliness problem for a given set of tardy jobs. Finally, we discuss the use of the latter algorithm in generating all efficient schedules.

Subject Keywords

Marketing, Management Science and Operations Research, Strategy and Management, Management Information Systems

URI

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

Journal

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY

DOI

https://doi.org/10.1057/palgrave.jors.2601478

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria Ozlen, M.; Azizoğlu, Meral (Informa UK Limited, 2011-01-01) In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the follo...
Scheduling parallel machines to minimize weighted flowtime with family set-up times Azizoğlu, Meral (Informa UK Limited, 2003-01-01) We describe and evaluate several branch-and-bound algorithms for an identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted flowtime. The algorithms differ by choice of lower bound method. Computational results suggest conditions favourable to a particular algorithm as well as the range of problem sizes that can be optimally solved in reasonable CPU time.
Multi-objective integer programming: A general approach for generating all non-dominated solutions Oezlen, Melih; Azizoğlu, Meral (Elsevier BV, 2009-11-16) In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical epsilon-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical epsilon-constraint method on the bi-objective integer programming problem for the sake of comple...
JOB-SHOP SCHEDULING UNDER A NONRENEWABLE RESOURCE CONSTRAINT TOKER, A; KONDAKCI, S; ERKIP, N (JSTOR, 1994-08-01) In this paper we consider the job shop scheduling problem under a discrete non-renewable resource constraint. We assume that jobs have arbitrary processing times and resource requirements and there is a unit supply of the resource at each time period. We develop an approximation algorithm for this problem and empirically test its effectiveness in finding the minimum makespan schedules.
SCHEDULING UNDER A NONRENEWABLE RESOURCE CONSTRAINT TOKER, A; KONDAKCI, S; ERKIP, N (Informa UK Limited, 1991-09-01) This paper examines a single-machine, non-renewable-resource-constrained scheduling problem where jobs have arbitary processing times and resource requirements. Unit supply of a resource is assumed at each time period. Performance criterion is makespan. It is proved that this problem is identical to the two-machine flowshop problem, enabling the use of Johnson's algorithm. Immediate extensions of this result are presented.

Citation Formats

M. Azizoğlu and S. Koksalan, “Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed,” JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, pp. 661–664, 2003, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/35694.