Optimal scheduling in film production to minimize talent hold cost

Edwin Tai Chiu Cheng; J. E. Diamond; B. M T Lin

doi:10.1007/BF00940554

Optimal scheduling in film production to minimize talent hold cost

Edwin Tai Chiu Cheng, J. E. Diamond, B. M T Lin

Research output: Journal article publication › Journal article › Academic research › peer-review

32 Citations (Scopus)

Abstract

The problem of minimizing the cost due to talent hold days in the production of a feature film is considered. A combinatorial model is developed for the sequencing of shooting days in a film shoot. The problem is shown to be strongly NP-hard. A branch-and-bound solution algorithm and a heuristic solution method for large instances of the problem (15 shooting days or more) are developed and implemented on a computer. A number of randomly generated problem instances are solved to study the power and speed of the algorithms. The computational results reveal that the heuristic solution method is effective and efficient in obtaining near-optimal solutions.

Original language	English
Pages (from-to)	479-492
Number of pages	14
Journal	Journal of Optimization Theory and Applications
Volume	79
Issue number	3
DOIs	https://doi.org/10.1007/BF00940554
Publication status	Published - 1 Dec 1993

Keywords

branch-and-bound algorithms
NP-hardness
Scheduling

ASJC Scopus subject areas

Control and Optimization
Applied Mathematics
Management Science and Operations Research

More information

10.1007/BF00940554

Cite this

@article{5509dec1a60046baa14b3d6214606252,

title = "Optimal scheduling in film production to minimize talent hold cost",

abstract = "The problem of minimizing the cost due to talent hold days in the production of a feature film is considered. A combinatorial model is developed for the sequencing of shooting days in a film shoot. The problem is shown to be strongly NP-hard. A branch-and-bound solution algorithm and a heuristic solution method for large instances of the problem (15 shooting days or more) are developed and implemented on a computer. A number of randomly generated problem instances are solved to study the power and speed of the algorithms. The computational results reveal that the heuristic solution method is effective and efficient in obtaining near-optimal solutions.",

keywords = "branch-and-bound algorithms, NP-hardness, Scheduling",

author = "Cheng, {Edwin Tai Chiu} and Diamond, {J. E.} and Lin, {B. M T}",

year = "1993",

month = dec,

day = "1",

doi = "10.1007/BF00940554",

language = "English",

volume = "79",

pages = "479--492",

journal = "Journal of Optimization Theory and Applications",

issn = "0022-3239",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Optimal scheduling in film production to minimize talent hold cost

AU - Cheng, Edwin Tai Chiu

AU - Diamond, J. E.

AU - Lin, B. M T

PY - 1993/12/1

Y1 - 1993/12/1

N2 - The problem of minimizing the cost due to talent hold days in the production of a feature film is considered. A combinatorial model is developed for the sequencing of shooting days in a film shoot. The problem is shown to be strongly NP-hard. A branch-and-bound solution algorithm and a heuristic solution method for large instances of the problem (15 shooting days or more) are developed and implemented on a computer. A number of randomly generated problem instances are solved to study the power and speed of the algorithms. The computational results reveal that the heuristic solution method is effective and efficient in obtaining near-optimal solutions.

AB - The problem of minimizing the cost due to talent hold days in the production of a feature film is considered. A combinatorial model is developed for the sequencing of shooting days in a film shoot. The problem is shown to be strongly NP-hard. A branch-and-bound solution algorithm and a heuristic solution method for large instances of the problem (15 shooting days or more) are developed and implemented on a computer. A number of randomly generated problem instances are solved to study the power and speed of the algorithms. The computational results reveal that the heuristic solution method is effective and efficient in obtaining near-optimal solutions.

KW - branch-and-bound algorithms

KW - NP-hardness

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=0027813731&partnerID=8YFLogxK

U2 - 10.1007/BF00940554

DO - 10.1007/BF00940554

M3 - Journal article

SN - 0022-3239

VL - 79

SP - 479

EP - 492

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

IS - 3

ER -

Optimal scheduling in film production to minimize talent hold cost

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this